Movement

So going along with entities, I think now I’m finally ready to start introducing basic AI into the game. And by basic AI, I mean “stuff needed to prepare for actual pseudo-state machine behaivor”. A series of posts here went through a bit of discussion about the A* algorithm for path finding and alternatives. Well after trying A* and, though this explains it really nicely, I couldn’t fully wrap my head around implementing an astar(start,end,gridmap) function and examples of it had a significantly lengthy set of code.

So looking at that other thread, it looks like a ‘scent’-based tracking system might work better. Specifically what I’m thinking of is that collaborative diffusion method talked about in that very first link. It seems simple enough, in that you just recursively flood fill an area to a certain depth with values, and other entities walk through the lowest/highest values it comes across to reach the player. Now the collab link overhypes the design a little much–the 2 pacman ghosts appear to be collaborating because each time anything happens, pacman’s “scent” map is updated and takes into account the moving entities to block off the scent paths, and an A* algorithm that is continually called like that I imagine would have the same effect.

That said, implementing this scent pathfinding is already proving to work with–I’ve already got something up that generates a very basic map, and to create boundaries, simply give the boundary tiles a very high scent value–anything higher than the currently examined value is ignored in calculating the scent map. The net result from just a plain area with no obstructions yields:


000000000000000100000000000000
000000000000001210000000000000
000000000000012321000000000000
000000000000123432100000000000
000000000001234543210000000000
000000000012345654321000000000
000000000123456765432100000000
000000001234567876543210000000
000000012345678987654321000000
000000001234567876543210000000
000000000123456765432100000000
000000000012345654321000000000
000000000001234543210000000000
000000000000123432100000000000
000000000000012321000000000000
000000000000001210000000000000
000000000000000100000000000000

Where each number is the ‘scent value’ of the tile. Adding in obstructions works, but representing it with 0-9 is hard to read. From there it’s a simple matter of if Entity.IsOnAStinkyTile: FindStinkierAdjacentTile;MoveToStinkierTile.

Grab it here.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: