Moving on 3d terrain
Author
Hi there!
I am developing 3rd person 3D game where you can control player over 3d terrain (only one layer, there won't be tunnels, bridges with space under them, building with multiple levels etc...). You will send player to some place by clicking mouse on that spot on terrain.
I would like use some simple pathfinding algorythms (any specific suggestions?) by projecting my terrain onto 2d plane (by eliminating height coordinate) and finding shortest path in 2d. There will be some obstacles, in form of objects, walls, steep slopes...
My question is how is this handled usualy? Is there some kind of accesibility map? Is it computed on the fly or precomputed and saved along with terrain? What about some enemy blocks only way, should I somehow update this accesibility map?
Any answers and tips are appreciated :)
(disclaimer: I know very little to nothing of AI algorithms, this is just how I look at this problem.)
There are two issues at play here. One is pathfinding, the other is how to do 2D pathfinding in a 3D environment.
Because you only have one level to deal with, you can pathfind as you would in 2D. If you have a grid of tiles, each with attributes like "very steep" or "has tree", pathfinding is very easy - find the shortest distance between the current point and destination, and then construct a path to said point, being sure to work around tiles that are unusable (too steep or has obstacles).
Making this 3D then becomes very easy. You can just adjust player height for the height of the tiles when you actually move the player, because at this point you already know where the player can and can't go.
There are two issues at play here. One is pathfinding, the other is how to do 2D pathfinding in a 3D environment.
Because you only have one level to deal with, you can pathfind as you would in 2D. If you have a grid of tiles, each with attributes like "very steep" or "has tree", pathfinding is very easy - find the shortest distance between the current point and destination, and then construct a path to said point, being sure to work around tiles that are unusable (too steep or has obstacles).
Making this 3D then becomes very easy. You can just adjust player height for the height of the tiles when you actually move the player, because at this point you already know where the player can and can't go.
Author
unfortunately I don't have tile-based terrain, obstacles can be anywhere, so I think I need something different
Hi,
There are a lot of solutions available: it really depends on what are your needs and constraints.
Concerning the accessible surface, let me outline two solutions (more exist of course):
- set up path nodes on your terrain: either simple spots with an influence radius or area spaces (rectangles for example). Pro: easy to set up in an editor. Cons: traveling units may always use the same path linking two nodes (needs some work to remove artificiality), world collision must also be handled (obstacles may need bounding boxes in case an avatar stray away of the path).
- simplify your 3D terrain into a navigation mesh: keep only faces without any obstacles. Pro: traveling units may use the full map area, world collision information is included within the nav mesh. Cons: Modeling a navmesh is a work on its own.
Regarding the pathfinding algorithm:
- precompute pathfinding info from one place to another: your editor computes once and for all every shortest path from one place to another. Pro: faster pathfinding in game. Cons: Difficulty to manage dynamic obstacles (there are workarounds though).
- compute on the fly pathfinding: using the algorithm of your choice you compute a path on demand any time there is a path request to avoid a dynamic obstacle or to simply travel from one place to another. Pro: may handle better dynamic obstacles (also depends on your depiction of accessibility). Cons: path computation is intensive.
There are many articles on the subject of pathfinding:
- at GameDev
- on Gamasutra
- look also the Game Programming Gems books (vol 1 and 3 for example).
Hope that helps.
Ghostly yours,
Red.
There are a lot of solutions available: it really depends on what are your needs and constraints.
Concerning the accessible surface, let me outline two solutions (more exist of course):
- set up path nodes on your terrain: either simple spots with an influence radius or area spaces (rectangles for example). Pro: easy to set up in an editor. Cons: traveling units may always use the same path linking two nodes (needs some work to remove artificiality), world collision must also be handled (obstacles may need bounding boxes in case an avatar stray away of the path).
- simplify your 3D terrain into a navigation mesh: keep only faces without any obstacles. Pro: traveling units may use the full map area, world collision information is included within the nav mesh. Cons: Modeling a navmesh is a work on its own.
Regarding the pathfinding algorithm:
- precompute pathfinding info from one place to another: your editor computes once and for all every shortest path from one place to another. Pro: faster pathfinding in game. Cons: Difficulty to manage dynamic obstacles (there are workarounds though).
- compute on the fly pathfinding: using the algorithm of your choice you compute a path on demand any time there is a path request to avoid a dynamic obstacle or to simply travel from one place to another. Pro: may handle better dynamic obstacles (also depends on your depiction of accessibility). Cons: path computation is intensive.
There are many articles on the subject of pathfinding:
- at GameDev
- on Gamasutra
- look also the Game Programming Gems books (vol 1 and 3 for example).
Hope that helps.
Ghostly yours,
Red.
Author
Thanks for info. I was thinking about path nodes lately, I heard HL2 had some decent pathfindign system, I'll try to look for some articles about it and about anything that would help :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
