-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|704|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
SoCoder -> Article Home -> Advanced Techniques

 
Jayenkai
Created : 02 January 2018
Edited : 02 January 2018

Expanded Grid Pathfinding
I'm sure there's a better name for this, which probably already exists, but this is a method that I've evolved since doing Army of Flags, and it seems to be working well for me and my enemies!

Thought I'd share.

Assuming your 'world' fits into a simple grid array, create a secondary array for pathmaking and a third to act as a buffer.

Every 10 frames or so, copy the pathmaking array to the buffer, then clear out the pathmaking array and start afresh.
(We'll call this ClearFrame)

To build the pathmaking array, start with all 0's, except for a 1 at the location of the thing you wish to find (eg, The player's location)

Over the next number of frames, do an expanding loop.
LookUp is our value for 'expansion', and should usually go from 2 to 'ClearFrame*Distance of Intelligence'

For x=playerX-LookUp to playerX+LookUp (and again for Y)
Within this region, decide if a tile is accessible (if wall(x,y)==false)
If it IS accessible, and its value currently set to 0, look at the 4 adjacent tiles, to see if any of those tiles are 'LookUp-1'
If any adjacent tiles are 'LookUp-1' then set this tile to 'LookUp'.

eg, for the first loop, the four adjacent tiles to the player's location will be designated 2's.
The next loop will expand further tiles to 3's, and so on.

Do about 5 loops of this per frame. Enough to expand the region enough for enemies to find the tiles, but not too much that the for-loop ends up slowing your game down.

Once you reach 'ClearFrame', copy the values to the buffer array, clear the map back to 0's, and then you can start moving the AI based on the tile values in the buffer array.
If the enemy is on a numbered tile, and can see a lower-value (but not 0!) tile around them, and then simply move them towards that lower-value tile.

Repeating this will eventually lead directly to the player, so add elements of randomness, like reducing how often the enemies use the lookup tables, and guiding them directionless at other times.
You should find that the enemies do very good player tracking, as long as the player's within the 'visible' area, surrounding the player.


You might additionally like to add additional buffers to help enemies find weapons or maybe have AI CPU players that can hunt for other targets, but in general I tend to just use this as a 'All enemies targeting the player' sort of thing, as adding more and more layers becomes slightly chaotic, and can cause slowdown in the game.

 

Comments
Tuesday, 02 January 2018, 18:20
HoboBen
 		This is Vector Field Pathfinding! Good stuff!
Tuesday, 02 January 2018, 18:32
Jayenkai
 		Vector field? What a silly name. It’s SO obviously a Grid!!! Who makes these things up??
Tuesday, 02 January 2018, 23:26
Pakz
 		It looks like floodfill or seedfill pathfinding to me. Also called dijkstra maps I think.