Interesting Pathfinding Question

Game Mechanics Artificial Intelligence
#1

I have been playing around with the thought of doing path finding without a grid. Something like the swarm applet, but instead, you click on a point on the screen and the elements will move to that place, but not overlap as they move, as well as, no overlapping when they arrive to the spot, or close to it if they can’t move all the way to the point. The only obstacles will be the units themselves, the map is open.

I have not given TOO much thought on this so I decided to come here and make a post and see if someone has attempted this and can give me some 2 cents. I am going to start planning it tomorrow as I am pretty tired.

So any ideas or thoughts on this idea?

Thanks

#2

some nice applets that demonstrate steering and flocking behaviors over at http://www.red3d.com/cwr/steer/

#3

Those are some very nice demos. Thank you for showing them to me. There was a link to both a paper and to a C++ library, I will have to check both out and get back to you!

#4

Alright, lets see if I can get the logic down for this:

Case: I am moving an object in a field of other moving objects. The user decided where these objects are moving, like in a typical RTS game.
High Level Logic:
1.) During each tick of the movement cycle, I look at each object.
2.) When I look at each object, I see if anything will intersect during it’s current direction.
2.1.) I can do this by stepping through the future based on the current speed of both parties. If at any point they intersect, do something to avoid it.
2.2.) To avoid the detected collision. I somehow have to choose what the two parties will do.
2.4.) I want to ensure that objects never move faster than their max speed. Generally, the objects will always be moving at their fastest rate. This means that I have to deduce the time it will take the objects to reach their intersection point. I have already done this in 2.1. I can then calculate which one to slow based on the distance.

Problem: What if I detect more than 1 collision with the same object and then I decide to slow it when it’s speed should not change? Example: Object 1, 2 and 3. Object 1 will have a collision with 2 and 3. Upon looking at the cases, in sequential order I determine the following:
Object 1 vs 2: Object 1 remains constant while Object 2 slows down.
Object 1 vs 3: Object 1 slows down while Object 3 remains constant.

So now my previous calculations are not correct. How do I avoid something like this situation? With a large set of units in a close area, this looks to be very difficult to solve. Though, I suppose if the objects are not moving very fast then the amount of collisions are very low.

I have some other cases, but I will post those up after we talk about this one :slight_smile:

THANKS!

#5

You can use osbtacle avoidance when: maps are open and obstacles are small and have no dead ends. You can then just got direct path to target and avoid anything you encounter along the way.

When you have open areas connected by small portals, find your way from portal to portal.

But on complex terrain, you’ll need real pathfinding. As a rule of thumb, you need real pathfinding when the direct path can lead to dead ends and obstacles which you cant go around. Hell, I cant tell convex and concave correctly :slight_smile:

-JAW

#6

OMG!!! I honestly cannot believe that no one has thought of something so simple as Graph Theory! has no one ever heard of this??!!!

If you havent, graph theory finds paths from one point to another based on things like whether or not you tank can get you point A to point B. It then tells you the path length. If you know the shortest path length and you can find other path lengths from other points to yet more points, you can then compute the points the tank would need to go to in order to get to its final destination, point C.

i know my definition is slightly… vague… but look it up in greater detail online and you’ll see the light!.. hopefully… if you cant seem to find the light maybe ill post somthieng in great detail on how to path find.

if no one has thought of this previous to my post… i feel kinda let down at the world. I mea really… how many people went to school for this kinda thing and here i am, solving things on my for people suposedly vastly my seniors.

#7

Pathfinding is done with graphs in computer games. Nothing new mate!

#8

This is more than just path finding. When you are dealing with a world that is constantly changing your approach is completely different than just trying to find a route as any route you find will change over time.

To approach such a problem as a swarm you must develop (a) swarm behaviour, (b) some form of anticipation system to second guess the likely movement of the swarm in general and © awareness of your position in a large crowd. Take for instance a funnel or a road junction, eventually some people will have to either slow down or stop to let others pass or you end up with a jam situation. We have all seen human beings create traffic jams in situations where common sense will tell you that actually stopping and letting other cars pass will make your journey faster.