Jump to content
  • Advertisement
Sign in to follow this  
spideroncoffein

*Confused* Pathfinding Approach

This topic is 2752 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

Hi Guys!

I'm not only completely new to this forum, but also to game development in general. So, for educational reasons, I have to do a 3D-Game, with graphics-engine built from scratch. Well, I'm OK with that. AND we are allowed to use any library (C++) that's not related to graphics or rendering. ;)

A colleague and me are planning to do a 3D-Real Time-Strategy game where you navigate (almost) freely in a 3D-room. Physics itself are clear to me at this point (Newton gravitation, speed, acceleration, vectors, mass). But pathfinding with this many factors screws up my brain. So, I read about 20 articles and 10 discussions mostly pointing at the A*-algorithm (in any variant). But since I don't have any experience in this field, it's mostly ghibberish to me. :blink:

Now, we plan to have the player make waypoints. But how to we get the path - around obstackles, through obstacles that slow you down, and the biggest issue: around and passing obstacles that have a mass big enough to have gravitational influence? We only need to calculate the path once, since all objects that have gravitational influence will be static, but it has to be the nearly shortest path in all 3 Dimensions. Collision is a completely different issue and will not be relevant to the path itself. Also, it is not required to have a "best" path, an approximation is enough. We don't know if we will have a delay on rotation (that would further complicate the issue), but let's say for now orientation of the object itself is not an issue.

So, here are my questions:

1. Can A* handle multible waypoints to interpolate a (approximated) path, even including obstacle circumventing? Or can any other pathfinding algorithm achieve that in real-time?

2. Can A* (in general) integrate factors like mass, acceleration, speed (at start of the path) and gravitation? Or is there a variant of A*or even a library that already integrates mass, acceleration, speed and gravitation?

4. Is there a different algorithm than A* or variants, or a library that is capable of handling all of these requirements (waypoint interpolation, obstacle circumventing, mass, acceleration, speed, gravitation)?

Please tell me if those requirements is like dreaming of world peace! :lol:

EDIT: I also thought about doing it completely myself, with stuff like impementing a cubic hermite spline, bezier curves and so on, but I don't really know how to integrate gravitation (especially the change of speed) or obstacle evation into this. But since the obstacles are (at this point) only spherical, wouldn't it be possible to calculate waypoints from the radius + safe distance to evade those?

Greetz,
Spider

Share this post


Link to post
Share on other sites
Advertisement
A* has enormous potential, it is most commonly used in grid arranged worlds to go from point A to point B in the shortest (ish) possible path accounting for passability and if you wish to, cost of navigation as well.

To navigate a grid world in 8 directional movement you most certainly need a waypoint list to represent the path, so that is pretty much basic need of the algorithm.

As for the cost variations and the physical factors you speak of, the A* calculates each desirable next step to add to a path by an heuristic formula, if you manage to represent these factors in a floating cost value the algorithm will resolve the rest for you, A* can be use even to make some AI decisions like for instance making a defenseless peon avoid known dangers when navigating, you just add the danger factor as a weight in the navigation cost and the affected tiles become less desirable for the algorithm.

I've never implemented A* for open 3D worlds but the principle is pretty much the same, I've heard of a couple of games that split their 3d world into a regular grid (half the size of the main actors) and do A* over that.

A* gives you the basic mechanic, you must then add optimizations accordingly to your project, if for instance your game is a maze of rooms and hallways, you should add a zone identification to your grid making the search much more simple, you do pathfinding within a room and if the order goes to another room you pathfind the door that leads to it and from the door you pathfind the target, you might even pre process paths between doors toy avoid processing known paths over and over again.

Share this post


Link to post
Share on other sites
If you're allowed to use ilbraries, maybe you'd like to look at something like Recast and Detour for pathfinding. While you would still have to do your own magic as far as acceleration etc... it might still give you a good place to start. It implements full 3D pathfinding using a navigation mesh.

Share this post


Link to post
Share on other sites
This will most likely not solve your problem, but might help out.

What you need to understand, is that A* is nothing more than a shortest path algorithm that uses an heuristic to orient the search in a graph. Nothing more.

What you CAN do, is have your heuristic take into account external factors, such as your speed, gravity, etc... and come up with different costs for each node of the graph.

If you want your pathfinding to be fully 3D, your graph topology will need to reflect that... look into octrees.

What's common is that you will tag EDGEs between nodes with a cost, so to move from node A to B, it costs 4 for example... if you have an obstacle that slows you down, make sure an edge goes through it and make its cost higher, like 6. Therefore, if it's shorter to avoid the whole thing, the path returned by A* will do it, otherwise it will go through the obstacle.

I would advise that you first master pathfinding before trying to add parameters like your mass, acceleration, speed and gravitation.

Hope this helps

Eric

Share this post


Link to post
Share on other sites

If you're allowed to use ilbraries, maybe you'd like to look at something like Recast and Detour for pathfinding. While you would still have to do your own magic as far as acceleration etc... it might still give you a good place to start. It implements full 3D pathfinding using a navigation mesh.

Recast is great even if you're using your own custom A* implementation. I used Recast to generate the nav mesh, then modified the source to export .obj files (source and executable here), which I then imported into my game. This was fairly easy because I was already using Blender, which could translate between the different formats I used.

My game code then went through the navigation mesh triangles, turning it into a simple graph that I could traverse with A*. I realized that the quickest way through a navigation mesh will always put you at the corners. So when traversing the graph, my algorithm would just pick the closest corner and add it to the list of waypoints. I would then go back through the waypoint list and remove any unnecessary points. i.e. if there are three consecutive points and I can remove the middle one without having the path go outside the edges I'm allowed to traverse, then I'll remove that middle point.
The project was open source, so you can view my code for this right here (written in Python). Cheers!

Share this post


Link to post
Share on other sites
Thank you, Guys!

So, as far as I understand it, if I can formulate my factors into weights, A* will find the shortest path - so basically, anything, from gravitation and acceleration to rotation is just a matter of defining as a weight. So, if it costs extremely much to make a hard turn, A* will simply try to avoid that. Octrees sound good, but since we want completely free navigation in a 3-Dimensional space (except for obstacles), the resolution of such an octree might kill the performance. Also, maybe it isn't necessary to calculate ALL of the factors, since it would make navigation too easy.

Well, I'll look into it, and if I can do the trick with reasonable performance, I'll tell you.

Greetz,
Spider

Share this post


Link to post
Share on other sites
If you're in free space with shapes to avoid, take a look at steering behaviors, you might not even need path finding...

http://red3d.com/cwr/steer/

Share this post


Link to post
Share on other sites
Hi there.
I would try using A* for waypoint , obstacle circumventing static ones, and for your mass, acceleration, speed, gravitation. That would be in a motion class that vectors to locations based on the path the A* class gives out.

Share this post


Link to post
Share on other sites

Hi there.
I would try using A* for waypoint , obstacle circumventing static ones, and for your mass, acceleration, speed, gravitation. That would be in a motion class that vectors to locations based on the path the A* class gives out.


I'm sorry but I fail to understand how that's helping? I really don't see how you're handling mass, acceleration, speed or gravitation.

One problem I see with that is that you need to simulate the movement during the pathfinding to have a proper cost for your node. This will most likely be too expensive.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!