I am working on AI snake that competes with a number of other snakes. My main problem is that my snake is keep boxing itself into its own body and sometimes it gets boxed by other snakes.
-
2Did you have a question? – Nick Johnson Oct 4 '12 at 10:14
Try thinking a few steps ahead. Brute force all possibilities for 2-3-4 (however many you can squeeze in before you notice lag) moves ahead. These shouldn't be a lot, because there are only 3 positions the snake can turn to at any given time. So if you check k
steps ahead, you will need 3^k
operations, and this is not counting the pruning you can do: don't check obviously blocked positions etc.
Pick the path that (not necessarily in this order, you will have to experiment - there is no silver bullet for this one unfortunately):
- lets you survive
- does not box you in
- gives you the most empty space around you
- whatever other heuristics you can think of that make one position better than another
Look into minimax and its variations. This should help you build a decent AI.
-
-
2@zista - you could probably find that using a Breadth-First Search (BFS). Number your snake from 1 to
k
, where 1 is the the tail andk
is the head. At stepp
in the BFS you can move over a piece of your tail ifp > piece_number
. But I don't think you need this, the fact that you look ahead will usually tell you if you are boxed in with no way out or not. If you want to find out beforehand, you can use BFS. – IVlad Sep 24 '12 at 13:59 -
@zista - not sure if you figured it out or not, but: as the snake advances, its tail retracts. So if you seem boxed in at time
t
, the same might not be the case at timet + 1
. Byp
I meant your current number of steps in the BFS, and bypiece_number
the ID of the part of your tail that you are attempting to cross over. – IVlad Sep 24 '12 at 19:18