Hello, Recently I started writing an AI for the game Snake. I can easily find a path to the food but the problem is that the path should leave space to maneuver after the food is taken so the snake doesn''t eat its tail or bump into a wall. However, I cannot think of a way to define space to maneuver. Does know how I might accomplish this? Thanks. - lmov

Check this out

http://www.gamedev.net/reference/articles/article1175.asp

You might not want to use genetic algorithms for your snake game, but this paper might give you a few ideas on how to solve some of the problems you''re having.

Before you write any AI algorithems you must take a pencil and paper and sketch your game screen. Then look at all of the possible conditions that the snake could face. From there you write your AI.


Hey, don''t forget to visit my page... by clicking here!

quote: Check this out

http://www.gamedev.net/reference/articles/article1175.asp

You might not want to use genetic algorithms for your snake game, but this paper might give you a few ideas on how to solve some of the problems you''re having.

Thanks, but I want to create the algorithm myself. It''s just for fun really.

quote: Before you write any AI algorithems you must take a pencil and paper and sketch your game screen. Then look at all of the possible conditions that the snake could face. From there you write your AI.

I cannot do this. I don''t think you know what snake is so take a look here: http://www.smallgames.com/znake/ It''s simply impossible to enumerate all the possible conditions.

- lmov

*Removes ignorant post after re-reading topic *

[edited by - Grizwald on November 30, 2002 9:11:03 AM]

i would probably try dividing the free space into a small number of rectangles

common sense: "i should get to food while maximising the reachable space afterwords"

carving up the board not only reduces the search space, but gives easy weights (area) and are probably easy to merge once the tail passes completely between them. as the head moves, the rectangles are split into smaller -less desirable- ones. hopefully leaving large areas accessible is then emergent.





as a tangential thought...

since the board is 2D, maybe stacking the future mazes as height into a 3D maze problem instead of 2D-over-time problem would be simpler. then you can merge future identical mazes (if the tail takes more than one tick to clear a gap between two mergeable rectangles, you can skip that tick). i think this makes it easier to visualise the problem...

example:

 _|_| = 1 board square_______  <- tail moving this way------ |  ----     | | |  A  | | |  B     | | |------    ----- 

this is probably a bit hard to see but here it will take 5 game ticks before A and B can be merged, the board won''t change and so you can prune 5 large branches of any time dependant search tree

after A and B have been merged, AB may be mergeable with the one above so count the length of the tail and even if they don''t merge, you can wait X ticks before the tail passes and the next pair of potentially mergeable areas is available

i am a snake. i am in a tower building. each floor has a slightly different maze. in one room of each floor there is a goal. the rooms are of varying heights. i can move one square sideways and one up each turn. is height more intuitive than time?

********


A Problem Worthy of Attack
Proves It''s Worth by Fighting Back

Actually, I think I have thought of a perfect snake algo. It even allows for not knowing where the food is.
The snake must begin in a corner. From there, the snake travels in a sweeping motion, say up and down, covering every possible square in a systematic way, except the topmost an bottommost row. Leaving the topmost and bottommost rows out allows the snake to return back to the opposite side of the board and repeat it''s sweep. In this way it maximizes the room it uses.

damn, I''m smart.

quote: Actually, I think I have thought of a perfect snake algo. It even allows for not knowing where the food is.
The snake must begin in a corner. From there, the snake travels in a sweeping motion, say up and down, covering every possible square in a systematic way, except the topmost an bottommost row. Leaving the topmost and bottommost rows out allows the snake to return back to the opposite side of the board and repeat it''s sweep. In this way it maximizes the room it uses.

I thought of that, but that''s cheating.

Right now I''m thinking of doing a standard breadth-first search to the food with the additional condition that after the food is taken it should be possible to move to all other empty locations (possibly do this recursively, but it will probably get too expensive). It will also be nice to tell the user: "The snake will die in X steps. Would you like to try to save it?"

- lmov

quote: Original post by lmov

I cannot do this. I don''t think you know what snake is so take a look here: http://www.smallgames.com/znake/ It''s simply impossible to enumerate all the possible conditions.

- lmov

Oh, come on, I saw the game. It doesn''t look too comlicated. Of corse you can do this.

>I''m thinking of doing a standard breadth-first search to the food >with the additional condition that after the food is taken it
>should be possible to move to all other empty locations

I think you''ll end up with the same result as the algorithm capn_midnight presented, especially when the snake gets longer and longer. You will need to do a lot of experimenting to get your algorithm better than simply sweeping over the complete screen.

Maybe you should let the computer do the experimenting for you. And that''s what the GA''s are made for

david.