Jump to content
  • Advertisement
Sign in to follow this  
Kirl

Snake AI

This topic is 4148 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I've written a cpu controlled snake (see thread here) wich performs moderately good at best. It reaches lengths of about 50-120 in a 20x20 grid, wich seems quite poor but it's my first attempt at any such thing. So I was wondering what more knowledgable people would think of it, and how you would aproach something like this. I just jumped in, seeing if I could get it to work in the first place, and now it's working I'd like to improve it. Play battle snake If you want to see it's behaviour on it's own press any key, except the arrow keys.

Share this post


Link to post
Share on other sites
Advertisement
Well, in VS mode it beat me pretty well.
So I can't complain about that.
Tho I do think the fact that the screen wraps around really hurt for me... if you let it wrap and Scroll to keep the player centered, it *may* help, or just make it even more confusing...

Eventually when it died on its own, it was from accidentally boxing itself in.

Really, I think the current apple chasing algorithm its fairly good, it just needs a simple suicide check so that it doesnt chase an apple into a space accessible by only 1 open square (the one it fills in as it chases)
This sounds like it could be done using one of the many BFS searches(starting at the apple) or some kinda floodfill...

Given that this is a wrap-around screen, the best strategy once you get significantly long, is to simply travel row by row in a continuous 'scanline' over the board.... but that gets really really boring

Share this post


Link to post
Share on other sites
The wrapping is kind of central to this snake version, otherwise whoever would be closest to the 'apple' would get it, now you can still manage to reach it first by cleverly wrapping.

I read up on the searches you mentioned but I think JS is too slow to be doing something like that while moving the snakes, but I may give it a try though. Thanks for mentioning.

Scanline movement would of course be optimal but as you said also quite boring. I even read a GD Article on using GP to get an optimal movement algorithm for a cpu snake, but the results were far too repetetive and easy to spot the patterns. I added this cpu snake especially to avoid the inevitable zig-zagging and repetetive movements.

I was hoping there would be some kind of established AI technique's or aproaches to constructing cpu controlled opponents...


Any additional comments or advise welcome.

Share this post


Link to post
Share on other sites
Quote:
Original post by Kirl
The wrapping is kind of central to this snake version, otherwise whoever would be closest to the 'apple' would get it, now you can still manage to reach it first by cleverly wrapping.


Whoever's closest Still does get it first, wrapping the screen only means your calculation of distance to the apple is a little more abstract.
Notably, the AI snake seems totally oblivious to the complexity; it seems to be looking at the world entirely 'relativistically'. As a human it gave me major issues though, since its hard to judge visually whether the wrap path or direct path is actually shorter...


Regarding the snake entrapping itself.
how about a simple check -
if the square he is considering entering, is blocked on two sides, then it is possibly going to lead to a dead end
so at this point trigger the floodfill/lookahead procedure to see where it might lead

or an even simpler rule... if the proposed destination square is blocked on two sides consider it a risk
if the square at it's open side is again blocked on two sides, consider it a high risk
and if the third square beyond that once again is blocked on two sides, consider it a suicidal risk
if the 'blockages' are caused by the bodies of two different snakes, reduce the risk rating by half -since two separate snakes won't form a closed loop as likely as a single snake body would

-or some variation thereof; the main point being, if you think pathfinding or floodfill are too costly for JS, then some simple greedy checks might work instead

Share this post


Link to post
Share on other sites
You're right that the closest one should always get the pudding, but in this case the snake purposefully doesn't look at distance, only obstructions. Therefore as it is now, you can still outsmart the snake, by wrapping. I've probably tested it entirely too long/often (a recurring problem when determining difficulty) but I can now easily judge the optimal direction.


Thanks for the suggestion, that's along the lines I had started to experiment, but stopped after it became way too much. However, meaby a conditional floodfill might work nicely afterall.

I'm glad you're using the right terms, wich makes it so much easier for me to read up on. Precisely what I was looking for, multiple aproaches to specific problems.

Thanks a lot, I've got some reading to do. :)

Share this post


Link to post
Share on other sites
I had another thought,(though you might have already been thinking this)
The Tail of the snake indicates the 'inside' vs 'outside' of a set of looped walls; because the tail is where newly opened space will be appearing.

Thus, given a square that is blocked on 2 sides(by a single snake), it can either lead to a dead-end, or to your tail. So your floodfill/BFS can decide safety based on this.

For a square blocked on 2 sides by two different snakes, this dead-end loop condition is not as certain.(unless we assume the enemy snake is trying to box us in..) The tail-reachable condition seems like it would still be good though...



So if your own tail represents 'outside' or free space
does the enemy snake's head represent 'inside' or closed unsafe space?

Share this post


Link to post
Share on other sites
I understand the tail search idea, pretty clever, but I'm unsure what you mean with the last bit (last two lines)?

I'm first going to see how the simplest function to write, will work out. If more then x squares ahead are blocked at 2 sides, change direction, play around with x a bit.

Thanks for thinking with me, you've been very helpfull! :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!