Thoughts for 3D A* Pathfinding

gwihlidal
Unregistered
 
Post: #1
Some good ideas brewing here Smile

Since it's a multi-purpose 3D engine, we can implement both methods! Smile

Than the developers can aquire a preference to one of the two methods (FPS speed, ease of use, etc..)

Nice thing with A* pathfinding though, is that we can have "cost" values for the "tiles"

If there is a shorter path through rocky terrain and a slightly longer one through light grass, it takes the grass trail. This opens the door to many possibilities. For instance, you could set the "cost" a "road tile" to 0 and all surrounding tiles to a higher cost, and than have an NPC "walk" down the road and follow it exactly.

Lots of things to consider!

Thanks for the input,

Graham
Quote this message in a reply
Member
Posts: 70
Joined: 2002.07
Post: #2
Here's a little bit about how dim3 does it. It's doesn't.

Including specific pathfinding algorithms will basically lock-out people who either don't need it or have better ideas.

What dim3 offers is a linked lists of nodes; you can append information to the nodes (anything you want), parse it anyway, and travel along them in anyway. It's up to the game designer to implement the actual algorithms, and dim3 helps with find the shortest path from node to node, nearest nodes, nearest whatever, etc. functions.

Therefore, if you have something simple, like a creature that walks a path unless it sights you, you can do that. If you want something more complicated (like weighting), you can do that too.
Quote this message in a reply
Feanor
Unregistered
 
Post: #3
I think raycasting would fail because it might end up looking as though there were no way to go, if you were indoors. Unless you use it as part of a step by step approach.

I think I would take Brian's pre-defined path idea and use it as a partial solution. If you encode your maps with paths between rooms or other locations, then if an NPC deduces that it wants to go to another point, the first thing it does is follow the right path to get it close. This should be computationally cheap. I believe that the open-source bots which were added to Quake and Quake 2 (like reaper and omnibot) could even make their own paths by running the levels randomly at first. They of course were primarily mapping routes between power-ups. Anyway, once they knew a level, they didn't forget it.

But the needs of an RPG are different. Follow the leader or clicking on a point of land that's currently hidden might not immediately reveal the best route. And a pre-defined path is useless if the way gets blocked by a locked door, debris, or other characters.

The vast majority of 3D spaces are still felt as roughly 2D for characters trying to get around them. The trick is whether to predefine a bunch of 2D clear/blocked maps for various areas of your terrain, or try to have the A.I. create them on the fly by letting it cheat and read the terrain ahead. I suppose that's going to happen anyway.

If you want to be able to drop a character in a new place and have it immediately find a path to somewhere else, I think that it's just going to wander in approximately the right direction, avoid bumping into things (use a second bounding box for early warning avoidance of walls? It would have to be a weak tendency so the character could still get through narrow passages), and just hope for the best.

How do you find your way around 3D spaces?

b
Quote this message in a reply
gwihlidal
Unregistered
 
Post: #4
Working on a game engine with fellow developers (CEGL - You can see it in the iDG dev diaries) and time after time I've thought about how we're going to do the AI programming for in-game entities.

Biggest issue was terrain navigation. I've read all the materials and resources I could find on the A* and slightly modified D* algorithms, and it's a sinch. One problem though. 2D tiles are simple enough, but 3D landscape meshes throw a wrench into the highly optimized 2D algorithms. And to make things even more interesting, you need to check for 3D objects occupying a terrain "node"

Few ways I have found and figured out:

1) You could use intersection calculations and sends intersection rays from your player to all surrounding 20 cubes around you to check whether or not you "hit" anything before trying to plan your route, but this tends to be very processor intensive, especially with the vast amount of other calculations being run as well (culling, lighting, etc..)

2) My favorite. Organize your landscape meshes into a "fake" 2D grid. That way you could run 2D A* algorithms and generate a path relatively quickly. I use a large mesh of triangles forming a grid of quads. They represent your "2D" mesh (forget the Z values for now). You can now keep a list of objects within a "tile's" space and avoid it (close the node). How do you "walk" across this 2D tile grid though? Simple, make a function, for example, called Walk(float x, float y) and that function basically attempts to move your character towards the target, and with simple collision detection, keeping your character ABOVE the landscape. Granted though, this way does create some potential problems. If you have "overlapping" tiles (say the lip of a cliff is stretching high above a "node" below) it's kinda hard to keep track of where entities are in relation to this "node", as well as knowing which "node" we are aiming for (the one on the cliff or the one under it). This method also probably wouldn't work for multilevel buildings like a castle unless you make special modifications so the AI can travel up stairs and know the current floor)
Would only be used as a "hack" for speed on non-overlapping terrain.

Anyways, it's 2:30 AM here, and I just thought I'd rant before I finish burning out. Smile

~Graham Wihlidal
Quote this message in a reply
Jeff Binder
Unregistered
 
Post: #5
One game I've done used a navigation mesh, where the search nodes are connected triangles in 3D space. It took a lot of fiddling to get it to generate reasonable looking paths, though, and it adds more work for the level designer. However, it does work with hills and such.

Another, possibly better way I've been thinking of (I haven't implemented this yet, so I don't know what difficulties will come up):
- Start with a heightmap. This could represent outdoor terrain or stairways indoors.
- Place objects on it. These objects include, among other things, walls. They can exist at eny point, and can be rotated around the vertical axis. In the editor I plan to have walls 'snap' together, and then all rotate as one unit, making it easy to edit.
- Each object is shaped like a rectangle. Non-rectangular things are made up of multiple objects.
- The pathfinding nodes are points just outside the corners of each object. A line-of-sight navigation space is automatically generated bty the level editor (so any two nodes with a clear path inbetween are connected).
- Other characters in the game are represented by four pathfinding nodes, all around them. The LOS is updated dynamically. This can be pretty fast if you optimize right.
- For the purposes of line of sight, the object can be represented by a 2D rectangle. In fact, all the pathfingind is done in 2D.
- Now we can generate 2D paths. When a character moves along this path, their position is just mapped on to the height map. So the path follows the contours of the ground.

Anyway, that's just a thought. I had to get that down sooner or later Smile . I can't look at your project because iDG is down, so I don't know if this would be right for you. But LOS pathfinding a a good tecnique, because it's faster than a grid and allows more freedom in level design.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Space Based Games... Why are they not as popular? Your thoughts... carmine 5 5,965 Nov 7, 2008 11:10 PM
Last Post: TythosEternal
  Game Ideas: Your Thoughts Man With No Name 16 9,045 Mar 10, 2008 08:15 PM
Last Post: JustinFic
  Pathfinding Namoreh 12 7,181 Sep 3, 2002 01:22 PM
Last Post: ededed