Last updated 8/04/2000. Don't save this from any HTML editor other than notepad or DevStudio!

Using "Smart Pathfinding" Grids

Summary and Techno-Babble

Purpose:

Does smarter path-following by maintaining a set of localized grid areas that represent an approximation of the passable terrain in that part of the map, and using a modified form of the A* algorithm to find the best direct path to the target.

The grids are arrays of world coordinates and links to neighboring grid nodes. The world coordinate represents the point in the center of the node. The links represent entity passable transitions between nodes.

They are localized because they are confined to specific areas in the map. The areas are defined using a special entity ("path_grid_center") which uses it's bounding box to define the area where there should be nodes. It can technically be placed in Ion Radiant, but in practice should only be used in noxdrop.

Paths that have complete sections of space (e.g. two or more "path_corner" entities) inside any grid area will automatically cause the entity following the path to engage smart pathfinding when travelling that section of path.

Grid nodes cannot reliably move in real time once they have been processed at level load. The only way to do it is to move the node, then use the console command "ai_refresh", which is slow and not meant to be used often.

Invalid grid areas will be flagged as such, but still "compiled" and stored in memory for debugging.

The Process

What follows is an outline of the general procedure of putting a path grid in a map and making it work. Each step that is linked is be covered in detail below. I'm assuming that you already understand how noxdrop works so I won't bother explaining stuff that doesn't matter. Items that looks like:

1. ] some console commands

are, of course, meant to be typed at the console. The detail section about that particular item should answer any questions about the command. Just click on the number if its yellow.

(load the map)

1. ] ndstart

2. ] exec noxdrop

3. ] exec noxdrop_ai

4. ] ndclass path_grid_center

5. (hit insert and create the entity)

6. ] ndsetkey gridsize xx

7. ] ndsnap

8. ] ndsetkey lowest x

9. (place the box, resizing it to cover the desired area)

10. (doublecheck that all the path_corners you wanted to enclose are blinking)

11. (if you want to test the paths and see what they look like, make a note of the targetname or entity number of each of the path_corners you want to check out)

12. ] ndsave

13. (quit anachronox, recompile -onlyents the map)

(the rest of the items are for when you want to test your path)

14. (load the map)

15. (check the console after loading the map, cause there may be errors or messages about your new AI grids)

16. ] ai_info 2

17. (go to the place where your AI grid should be and check for errors)

18. (maybe use the ai_test command to see what the paths will look like)

The Details

]exec noxdrop_ai

This is an extra little config file that binds the keys you will use to setup the AI grids. The keys are illustrated in the following modified screenshots. Notice that they keys were meant to be used when looking at the grid from a specific side. If you want the keys to do what they say you have to be in the right place, or else it might not make any sense. But feel free to do it however you want, it will always work the same way (i.e. the 'N' key will always expand the box along the X axis, etc). (Also, These directions assume that you haven't rotate the entity at all (yaw = 0). "Behind" and "Left" are relative to the entity's arrow.)

When looking at the node from the left:

When looking at the node from behind:

]ndsetkey gridsize xx

Each grid has an associated gridsize. The gridsize, of course, defines how far apart the "lines" of the grid are, and how large each grid unit is. NOTE that if an entity cannot use a grid if it's size is smaller than the entity's bounding box size. When placing a grid you may have to do some research to find out what the largest entity will be trying to use the grid, then make a trade off between more grid resolution and the largest entity. Also, the larger the gridsize is and the more complex or tight the geometry is, the more chance that there won't be a clear path available for any two path nodes. In general, 32 is a good number. But you will need to make sure that's large enough for whatever particular situation you're working on.

]ndsnap

This takes the current entity and snaps it origin to lie on the nearest grid intersection. You need to do this in order to avoid having a grid with fractional rows or columns.

]ndsetkey lowest x

To understand what this means, you need to get a general idea of how the grids work. When the map starts, the AI system searches the map for any entities named "path_grid_center". When it finds one, it takes the entity's bounding box (the size you setup with the keys from above) and gridsize and calculates how many elements will fit along the x and y axes. Then it creates all those grid elements (nodes) and spaces them out in a grid along the top of the bounding box. Finally it pushes each node down, one by one, until it hits the ground. If it doesn't hit the ground or doesn't have ground under all four corners, that node is marked as impassable.

NOW, with that in mind... if the grid entity has a "lowest" key that is non-zero, during the process of pushing the nodes down into the ground, it will continue to push them down through the floor until it finds the lowest, passable spot that is not lower than the bottom of the bounding box. No nodes can ever be outside the bounding box you defined.

There is a gap here because the nodes get stuck on the inclined roof and are impassable.

Now everything is OK because the nodes went all the way down to the lowest point.

(place the box, resizing it to cover the desired area)

This is pretty straighforward once you get used to the funky keys. You move the box around in the map as you would any other entity in noxdrop. But you must use the keys from above to resize the box. Just play with it for a while until you get a feel for it. Now stop smiling because of that dirty joke you just thought of.

Oh, one other IMPORTANT NOTE: if your box is just all screwed up and you just want to start over, you can use "ndexpandbox reset" to reset the box back to the beginning position.

(doublecheck that all the path_corners you wanted to enclose are blinking)

When you have a path_grid_center selected, all the path_corners that are inside the box you defined will blink so that you can see when they are enclosed. BEWARE, however, because it's blinking doesn't guarantee in any way that that path_corner will have a valid path to or from it. It just means that it will be considered inside that grid when the map starts.

(check the console after loading the map, cause there may be errors or messages about your new AI grids)

There are three messages you should see during map load that are related to the path grids:

	AISmartpath_Init: Processing grid centered at (x,y,z)
	AISmartpath_SetParameters: overriding grid size (default size) with specified (your size)
	-----| AISmartpath_Init: Processed (total number of grids in the map) grids
	

	ERROR: AStar_Search got start == end
	AISmartpath_Init: snapped #(entity number) (x,y,z) to grid
	

]ai_info 2

Different levels of ai_info yeild different detail about the grid. ai_info 1 only shows paths as lines, along with the other ai_info stuff like path corners and such. An entity's path shows up as a thick green line (visible from the top), and the "ai_test" path shows up as a thick purple line. ai_info 2 will show the actual valid grid nodes and the links between them. ai_info 3 will show whatever debug info I happen to be playing with at the time of the last publish. It might be interesting but will be useless.

(go to the place where your AI grid should be and check for errors)

Take this screenshot for example:

The only way you would actually be able to tell that there was a gap there in your grid (thus making that path corner in there unreachable) would be to visually check it.

(maybe use the ai_test command to see what the paths will look like)

Use this command:

ai_test [edict number || targetname] [edict number || targetname]