Archived

This topic is now archived and is closed to further replies.

b3rs3rk

Pathfinding in a Quake-style world

Recommended Posts

b3rs3rk    216
i''ve wrote a small full 3d engine (like Quake) and now i would like to implement some AI for monsters and NPCs. The first thing is "pathfinding", so the problem is: i think i cannot use the A* algo because the world is in pure 3d and i cannot create a tile-system... so how can i do? i''d like to understand how pathfinding is done in quake and/or in others fps :/

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
They use waypoints, points that are connected to each other. There are articles here in GDNet, about path finding. Use Article search to find them.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
you COULD use A* using a 3 dimensional grid, no?
i imagine this would make for some very processor intensive pathfinding though... i suppose you could use it to automatically generate a bunch of waypoints pre-game though

Share this post


Link to post
Share on other sites
b3rs3rk    216
or i can use some kind of graphs: for example i could create a 2-dimensinal grid for every level and connect two leves (when there are stairs or elevator ) with a graph: every grid is a sub-root node ... i dunno if this makes any sense :P

Share this post


Link to post
Share on other sites
wolverine    358
Quote:
Original post by b3rs3rk
or i can use some kind of graphs: for example i could create a 2-dimensinal grid for every level and connect two leves (when there are stairs or elevator ) with a graph: every grid is a sub-root node ... i dunno if this makes any sense :P


It makes sense alright, but depending on how your engine is programmed (read designed), making this graph could be even a harder problem then the original one. What i mean is, what's a different level to you? Is it only, and only only, when you have stairs? What about slopes? Things like boxes over boxes. Or elevators. Or a piece of floor that isn't at a 0 degree angle. See what i mean?

The pathfinding you're trying to implement, is it dynamic? I mean the monster (or whatever) ears a sound somewhere and sometime and tries to find the path on the fly, or is it always the same and you can use some sort of A* when your compiling the level for precalculating?

Share this post


Link to post
Share on other sites
b3rs3rk    216
@wolverine: i got elevators, boxes over boxes, floor not at 0 angle, etc etc ^__^ THIS is the real problem :/

at first maybe i can start developing a static ai system with precalculate waypoints, but the main problem remain always the same: how can i structure the 3-dimensional grid?

Share this post


Link to post
Share on other sites
wolverine    358
This may be unfeasible (i'm just shooting in the dark :), trying to help ), but what about dividing your world in a octree kind of way and for every cube keeping information on wether you "can go to" to the adjacent cubes?

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
Quote:
Original post by b3rs3rk
@wolverine: i got elevators, boxes over boxes, floor not at 0 angle, etc etc ^__^ THIS is the real problem :/

at first maybe i can start developing a static ai system with precalculate waypoints, but the main problem remain always the same: how can i structure the 3-dimensional grid?


I haven't yet seen a game, where waypoint placement was automated. You need to place those waypoints by yourself... Bare with it...

Share this post


Link to post
Share on other sites
lc_overlord    436
waypoint placement is automated in quake(1-3).
the simplest way is probobly to do it yourself, it's not that hard if you have an editor to do it in.

Share this post


Link to post
Share on other sites
_DarkWIng_    602
A* is not limited to grid. It works on any kind of graph structure. 2D grid is only used in most tutorials becouse it is simple to visualise it and becouse heuristic (cost) function is easy to understand.

Share this post


Link to post
Share on other sites
ZMaster    240
If Quake1 features automated path-finding, why don't you get the Quake1 source? It's open source...

I also bet, there are alot of tutorials about path-finding on the net. Check google and/or www.gamasutra.com (they have several articels about path-finding).

Share this post


Link to post
Share on other sites
vnillabrent    122
Quote:
Original post by Anonymous Poster
I haven't yet seen a game, where waypoint placement was automated. You need to place those waypoints by yourself... Bare with it...


In AI Game Programming, there is an article titled Building a Near-Optimal Navigation Mesh that discusses one possible algorithm for waypoint generation. The author, Paul Tozour, worked on the AI for Thief 3 and MechWarrior 4: Vengeance. It's very likely that other commericial games automate their pathfinding also.

Share this post


Link to post
Share on other sites
hplus0603    11356
Automated path finding is possible, but hard. If you're a single person, and want to ship a game, going with hand-placed waypoints will save you lots of development time.

If you want to build automated information, you can do something like:

- Build information about each neighboring polygon for each polygon in the BSP tree.
- For each polygon, decide whether it is walkable. Typically, this means its face normal points less than 30 degrees or so off "upwards", and a player-sized ball resting at the center of the polygon will not intersect any walls/ceilings.
- Use the center points of the walkable polygons as your waypoints, and the connectedness information for those polygons as your waypoint connectedness.
- The cost function is linear 3D distance.
- Now, you can run pathfinding through A*, as long as source and destination are connected and walkable.

To deal with jumps, platforms, etc, you have to extend the waypoint generation with systems that allow for jumping travel, and elevator-call travel. This is doable, but a little trickier -- I'd suggest getting basic walking working first, and then it should be straightforward to figure out how to add different kinds of transition nodes between reachable polygons (and use different costs for these nodes).

Share this post


Link to post
Share on other sites
lc_overlord    436
Quote:
Original post by ZMaster
If Quake1 features automated path-finding, why don't you get the Quake1 source? It's open source...


About that, q1 is probobly a bad example,all though it does have some kind of simple automatic pathfinding, it's not used that mutch.
But the various bots written for quake do use a pretty sofisticated aproach.
Just take a look at the eraser bot for q2.

Share this post


Link to post
Share on other sites
RipTorn    722
I really don't think automated waypoint placement is a very appropriate idea, unless it's something like just letting a grid of waypoints fall out of the sky and seeing which ones end up in the level.. but this is likly to cause all sorts of problems with tight corners, etc.

Then there is the actual path-finding itself, so I'll assume you have hand placed your waypoints...

they first will need a list of all adjacent waypoints that can be reached (not line of sight - actually able to be walked to). This is a tough one.

then you could precompute your path finding I suppose...

say:

you have 100 waypoints in your map, which is probably quite a reasonable number, each will have an array of bytes the same length (100), indicating which waypoint to go to next, to get to waypoint n. (ie, to get to waypoint n, goto array[n]).. when you get to array[n], repeat. with a limit of 256 waypoints you'd use up 65k of memory which isn't all that much.

calculating this set isn't probably all that easy (well, it will just take a long time, brute force it would be O(n^3) or so I think...? anywho. but since it is a precomputed thing, then that solves all sorts of problems in run time...

?

Share this post


Link to post
Share on other sites