Testing game levels using JGap need help

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Testing game levels using JGap need help

rabidgremlin


Hi there,

I have a simple puzzle game that I'm working  for which I intend to procedurally generate a large number of levels for.

I decided to use GAs and JGap to play test these levels to prove that they are solvable and to gauge their difficulty.

I have a solution that solves simple levels without issue but it currently fails to find any solutions for more complex levels.

I believe my fitness function is the issue as it is not allowing the GA to hit on the right solution :-(

This diagram shows the best solutions for a number of levels. As you can see the last 2 (more complex) levels are not even close to a solve.

http://imgur.com/m5pgu

The game rules are as follows:

1) play is on a 5x5 grid, not all squares can be moved on to ( the white squares in the diagrams)
2) to complete a level the player must pick up all the gems by moving into their square
3) a player can move 1 square at a time in any direction (the 8 compass points)
4) each move the player makes substracts 1 from their total moves. If they run out of moves the game is lost
5) the player starts each level with a number of moves
6) each gem they pick up adds or subtracts moves
7) yellow gems are worth 3 moves
8) magenta gems are worth 5 moves
9) red gems are worth -3 moves

Currently my chromosomes consists of a number of integers. Each representing a player's move. Each gene can have a value of 0 to 7 representing a direction. 0 is north.

The chromosomes are n genes long where n is the maximum number of moves for the level, which is calculated by taking the starting moves and adding up all the values of the positive value gems.

The fitness function basically plays the level by walking the chromosome and making each of the moves represented by the genes.

If an illegal move is made (off the board or into an empty square) or the the player runs out of moves, the level is failed.

If all the gems are picked up then play stops and the level has been solved.

The fitness function also counts the number of direction changes made. Solutions that change direction less get a slightly better score.

For failed levels a score is calculated as follows:

GemsPickedUp * 10 + MovesRemaining * 10 - DirectionChanges * 0.25

For a solved level the score is the same but an additional 500 points are added.

So my questions are:

1) does my choice of genes make sense?
2) how can I make my fitness function better
3) can I do anything to the jgap configuration to improve things (I'm currently using the DefaultConfiguration)

Thanks

Jonathan


------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Testing game levels using JGap need help

Klaus Meffert-5
Jonathan,
 
there is a similar example packaged with JGAP, but it used GP and not GA as GP allows for more complex solutions.
Please see package examples.gp.anttrail, main class is AntTrailProblem.java
 
I think it would be best to modify the ant trail example to fit your needs.
 
Best
 


From: rabidgremlin [mailto:[hidden email]]
Sent: Thursday, April 12, 2012 11:34 PM
To: [hidden email]
Subject: [jgap-users] Testing game levels using JGap need help


Hi there,

I have a simple puzzle game that I'm working  for which I intend to procedurally generate a large number of levels for.

I decided to use GAs and JGap to play test these levels to prove that they are solvable and to gauge their difficulty.

I have a solution that solves simple levels without issue but it currently fails to find any solutions for more complex levels.

I believe my fitness function is the issue as it is not allowing the GA to hit on the right solution :-(

This diagram shows the best solutions for a number of levels. As you can see the last 2 (more complex) levels are not even close to a solve.

http://imgur.com/m5pgu

The game rules are as follows:

1) play is on a 5x5 grid, not all squares can be moved on to ( the white squares in the diagrams)
2) to complete a level the player must pick up all the gems by moving into their square
3) a player can move 1 square at a time in any direction (the 8 compass points)
4) each move the player makes substracts 1 from their total moves. If they run out of moves the game is lost
5) the player starts each level with a number of moves
6) each gem they pick up adds or subtracts moves
7) yellow gems are worth 3 moves
8) magenta gems are worth 5 moves
9) red gems are worth -3 moves

Currently my chromosomes consists of a number of integers. Each representing a player's move. Each gene can have a value of 0 to 7 representing a direction. 0 is north.

The chromosomes are n genes long where n is the maximum number of moves for the level, which is calculated by taking the starting moves and adding up all the values of the positive value gems.

The fitness function basically plays the level by walking the chromosome and making each of the moves represented by the genes.

If an illegal move is made (off the board or into an empty square) or the the player runs out of moves, the level is failed.

If all the gems are picked up then play stops and the level has been solved.

The fitness function also counts the number of direction changes made. Solutions that change direction less get a slightly better score.

For failed levels a score is calculated as follows:

GemsPickedUp * 10 + MovesRemaining * 10 - DirectionChanges * 0.25

For a solved level the score is the same but an additional 500 points are added.

So my questions are:

1) does my choice of genes make sense?
2) how can I make my fitness function better
3) can I do anything to the jgap configuration to improve things (I'm currently using the DefaultConfiguration)

Thanks

Jonathan


------------------------------------------------------------------------------
For Developers, A Lot Can Happen In A Second.
Boundary is the first to Know...and Tell You.
Monitor Your Applications in Ultra-Fine Resolution. Try it FREE!
http://p.sf.net/sfu/Boundary-d2dvs2
_______________________________________________
jgap-users mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/jgap-users
Loading...