Jump to content
  • Advertisement
Sign in to follow this  
BUnzaga

A neat idea regarding pathfinding weights.

This topic is 3889 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 am not sure if this has been presented before, if it has I am sorry for the waste of time. I am fairly new to the gaming world, and I am currently in school for a CS degree. I have been grueling over a good way to implement a path finding system and came up with the following equation: weight=(distance/(speed/work)) Rules: . work has to be greater than 0. . if work = 1, the weight is the standard rate of movement. . if work is less than 1, and as work approaches 0, the weight decreases. . if work is greater than 1, the weight increases. . if work is positive infinity, the node is impassable. Example: setup .tiles are 64x64. .The standard speed = 10 (tiles per second). .The work to traverse grass is 1. .The work to traverse swamp land is 1.5 .The work to traverse water is 2.0 .The work to traverse a road is .5 Now lets say I am crossing 4 tiles of each type in a straight line. For each situation, distance = 64x4 = 256. For grass: (256/(10/1)) = 25.6 = 2.56 seconds of travel For swamp: (256/(10/1.5)) ~ 38.4 = 3.84 seconds of travel For water: (256/(10/2.0)) = 51.2 = 5.12 seconds of travel For road: (256/(10/.5)) = 12.8 = 1.28 seconds of travel So from the simple example, the obvious choice is to take the road. Next being grass, then swamp, etc. So what is neat about this is that you can setup each tile to contain the work to traverse that type of tile, and then calculate the distance from currentTile to nextTile and have it automatically set the weight. Let me know what you guys think. BUnzaga

Share this post


Link to post
Share on other sites
Advertisement
i think that's a pretty good approach, and is reasonably common in pathfinding.

in 3d a simmilar method can be used by finding the gradient between tile A and B and factoring in this too (ie walking up a road would perhaps be harder than walking along some grass or down some muddy ground).

Share this post


Link to post
Share on other sites
Ahh that is a good point. So the final equation would be:

weight=(distance/(speed/(work+(slope/90))))

new rules:
. slope = an angle in degrees between 180 and -90.
. as slope gets closer to -90, the work is reduced, thus lowering the weight of the tile.
. As the slope approaches 180, the work is increased, thus increasing the weight of the tile.

So now say I am traversing normal grass (1.0), but at a 45 degree angle, the new 'work' is (1.0+(45/90)) = 1.5

Share this post


Link to post
Share on other sites
How you determine your weights depends on what your game needs. The core idea is that paths all have a cost, and that the cheapest path needs to be found (again, depending on the game - some games may settle for a less efficient solution, for performance reasons or otherwise). This may be the path with the lowest distance. Or the path with the lowest chance of enemy encounters. Or the path with the highest amount of goodies. Whatever you use as your criteria.

If your game doesn't use slopes, then why include them as a factor? If different units in your game handle terrain differently (a hovercraft can pass plains equally fast as roads, for example, while a jeep has more difficulty with plains, etc.), then why use a predefined work value per path? And why factor in a units speed anyway? This scales all weights equally, so it doesn't affect the outcome in any way.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!