Jump to content
  • Advertisement
Sign in to follow this  
arczev

pathfinding problems

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

I've recently implemented a A* pathfinding algorithm but I have some problems with that: 1: My pathes look like ----------S -----------* -------------* ---------------* -----------------* * * * * *G instead of ---------S -----------* --------------* * -------------------* * ------------------------* ---------------------------* G and how to fix it 2.How to efficiently deal with pathfinding of multiple units? 3. How to deal with pathfinding of bigger units which take up more than one node ( (for example vehicles)? thx 4 response :)

Share this post


Link to post
Share on other sites
Advertisement
1: Google for heuristics, which is an algorithm to help the pathfinder to guess the next move.

2: Either put pathfinding in it's own thread or do time/frame based divisions (i.e only let pathfinding take 100 ms each frame - if not complete, wait till next frame and continue then)

3: Multiple grids, or use node-based pathfinding instead of grid-based. You could easily link the grids together so that B contains four tiles from A for instance.

Cheers!

Pathfinding rocks! It's like magic to watch the little critters find their way around the maps! :)

/Robert

Share this post


Link to post
Share on other sites
Just thought of a crazy idea:

You could add a deviation-cost into the calculations...?
Imagine a line drawn directly between start and finish, and the further away from the line, the higher the cost (in addition the already calculated cost to the finish node). This SHOULD lead to units always trying to find a direct line towards their target.

It could create problems thou, since the agents may take longer paths than required to get to the target - especially if the obstacles are long thin walls for instance.

/Robert

Share this post


Link to post
Share on other sites
Why is path 1 incorrect? It's just the same as path 2 (distance-traveled and efficiency wise). Anyway, maybe try using Euclidean distance (just test it with Euclidean distance; I wouldn't recommend using Euclidean distance in the end seeing as it requires a sqrt).

I'm going to guess you want your path's to have some kind of constant slope when possible so that the unit can move in a straight path from A to B without being forced to use some path that makes its movement unnatural (meaning it is obvious it is on a grid). This is a bit of a problem though. If you're doing 8-directional A* pathfinding, you have to realize that movement is constricted to 8 directions. That means that if your unit is going from A to B, it will travel there using those 8 directions and only those 8 directions. If you want to be able to move in any direction, well, that's another problem which I unfortunately can't help much with.

Share this post


Link to post
Share on other sites
remember you dont have to take the sqrt for the distance if you're just comparing it to other distances. just use squared distances.

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!