Rivers using A* Path Finding

Because I’m lazy I dont want to have to describe the river courses on my landscape in terms of really detailed control points, so I decided to try using the popular A* pathfinding algorithm to do the work.

All I have to do is define the start location and the end location of the river, and then let the magic of A* do the rest. A* requires two basic parameters

  • The estimated cost of a given step
  • The true cost of a given step

In my case the estimate cost is just the distance between two given points;

Vector3 pointA;

Vector3 pointB;

float estimatedCost = (pointA – pointB).Length();

This will allow A* to rapidly reject the most expensive routes.

The true cost between two points is more complex, but based on the same algorithm. The true cost is the Estimated Cost (which is also the lowest cost) plus a modifier based on the particular kind of dynamics affecting river flow. In my case a really simple implementation is to check the relative heights of the two points; a river never flows Uphill so the cost of any particular step where the river would flow Uphill becomes float.MaxValue. Rivers like flowing downhill, and like to flow downhill the quickest way; so the cost of the step is EstimatedValue – (pointA.Y – pointB.Y) . This means the pathfinder will favour the steeper downhill slopes.

Because there are a LOT of options in making a river flow between two distant points (in fact in theory every possible route across the landscape needs to be checked) you might need to give it a hand by breaking rivers down in to a few control points, but this is far quicker than describing the river route by hand.

I got my A* library and some background information from this helpful blog;

Advertisements

One thought on “Rivers using A* Path Finding

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s