Public Group

# pathfinding problems

This topic is 3792 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 on other sites
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 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 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 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.

1. 1
2. 2
3. 3
Rutin
19
4. 4
khawk
14
5. 5

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633655
• Total Posts
3013187
×