Thread: fun with pathfinding

Well, I'm in the midst of some intense coding, but most of it is stuff I've already implemented, conceptually, in the past...I'm just trying to throw it all together for something useful.

I've been fiddling around with AI and pathfinding. I'm using the exact same constructs/concepts as when I posted this demo:

http://cboard.cprogramming.com/showthread.php?t=69595

except now I'm adding it to a 3D world. I use a quake3 editor (GTKRadiant 1.4) and quake3 bsps for the basic data and BSP compilation. I edited the entities.def script that the editor reads to determine what entities exist. I added an 'info waypoint node' entity which you place in the map:

Code:

/*QUAKED info_player_start (1 0 0) (-16 -16 -24) (16 16 32)
Player spawn location. It works in Quake III Arena, but it is not used in the Id maps. Use info_player_deathmatch instead.
-------- KEYS --------
angle : direction in which player will look when spawning in the game.
target : this can point at a target_give entity for respawn freebies.*/

//=============================================================================


/*QUAKED info_waypoint_node (.05 .5 .5) (-10 -10 -10) (10 10 10)
-------- KEYS --------
target : your mother
*/

So in the editor I just place these little goose-eggs around the world at critical points, and when my program loads the map it parses the entity file, saving the positions of the waypoint nodes. Then, it performs a line of sight test to fill in the row and column entries of a sparse connectivity matrix (a matrix that doesn't save the 0 entries, to speed up computation and decrease memory). It then raises these sparse matrices to n powers, determining what nodes you can get to at various steps. So far, it has turned out to be exactly what I wanted: an effective mechanism for using pre compiled constructs to minimize the amount that you need to do realtime.

So, when the AI agent needs to make a move, it can look up these values in the stored matrices (which require essentially nothing memory wise) and find the next move along the leg of a path, without having to know the entire path.

I'm still just ........ing around with things, but I posted a screenshot of a map I'm building to test these things

screenie

Each of the yellow spheres you see is a waypoint node. The red sphere (well, there's actually some ms3d model in the middle of it, I think it might be a bert model or a model sentral made for me) is actually a hovertank sitting on an air cushion, and the gray thing is a ramp that I was using to test the physics of the air cushion (I can command it to spawn above the ramp, upright, then when it lands on it it rights itself, slides down one side, and back up the other!!! woot! and it remains stable).

Umm yeah, I'm just happy that I'm making progress, thought I'd share. I didn't bother recording another video because it didn't exactly work last time I tried that.