Pathfinding - How to find a dead path?

Hey guys, I'm making a game with XNA and I've ran into a wall...

I'm using A* to find paths for my little bots, but since the terrain is ever-changing, I need to check continually if it is possible to get from Point A to Point B. Using A* to check is very CPU consuming (as I just need a true/false, if there is a path between two points). I've read that A* is the fastest method (better than gready-first or Dijkstra's) so I don't know any other option...

I don't know any algorithm that would be able to quickly calculate if a path exists between two points, short of flying.

Thank you.

HOLY SHIT ITS USER1!

A* is the fastest.

Best thing to do is calculate the algorithm every time the map changes, once. If it's like worms, just calculate from one side to the other, then jump inbetween.

If it's 3D you are on your fucking own.

Yeah but the map changes very fast, and I have multiple bots in various locations all heading toward to one exit. If i want to recalculate, all my bots (probably up to 20 at a time) will have to recalculate their paths. And then I have to check if all 20 bots can still go to the exit. If they are blocked, then the last map change will have to be undone. And no this is a 2D game. Obviously grids are the easiest for path finding so

I'd suggest not calculating their full path then.

Originally Posted by arunforce

I'd suggest not calculating their full path then.

Then what should I calculate to? This is my first game so I'm just kind of learning all of game coding... I'm pretty sure I'm doing a lot of things wrong

HOLY SHIT ITS USER1

Where have you been?

Originally Posted by Lolland

HOLY SHIT ITS USER1

Where have you been?

I've been programming this game and also at school.

Originally Posted by User1

I've been programming this game and also at school.

I know where ya really been

Holy shit its user1

I've just givven up on that and just let my bots get trapped, they'll die a lonely death anyway D:

Originally Posted by SmartAlley

Holy shit its user1

Originally Posted by Lolland

HOLY SHIT ITS USER1

Holy shit people are desperate for sigspace.

WB User1 by the way

Draw a line between those 2 points and check if the line is inside any other object. Using XNA + .NET libraries shouldn't be that hard. (i'm saying this because all you said was that you need a true/false like answer)

If you are actually calculating that path.. well.. ^^

show us some screens of what possible paths might look like, might come up with a custom pathfinding thingie lolol

Well I need to know if a path exists, it doesn't necessarily need to be a straight path.

Here is a quick video on my current progress, it isn't much so... yeah

Pathfinding - How to find a dead path?

Post a Reply

Tags for this Thread