Jump to content
  • Advertisement

Archived

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

b3rs3rk

Pathfinding in a Quake-style world

This topic is 5110 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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
Advertisement
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
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
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
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
@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
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
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
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!