Revisit 5 - Paths

Web log of development issues.

Revisit 5 - Paths

Postby adamsderk » Tue Jun 09, 2009 6:07 pm

Greetings,

Today is about pathfinding and roads.

Terrain is nearing its close. Ok, I still have some big stuff to do, but it is nothing compared to what it took to get this far.

For those of you not familiar with the terrain image from the last entry, here it is again in the upper left corner.

Image

Color refresher; red: mountains, orange: rough, dull green: flat, bright green: trees, blue: river, black: nav points, and yellow: roads.

The six images above show the progression during development. Numbered from left to right top and left to right bottom. 1 is the original river map. 2 includes a different river (had to keep the river from starting near either vertical edge for other map generations), forest areas (optional, but effect the road generation) and nav point selection (I pick a nav point in each of nine quadrants (3x3 grid) and use the top middle, left, right, and bottom middle). 3 was the first attempt at roads. Notice at the bottom where there are two roads next to each other, I wanted to get rid of that. 4 is roads where it was "easier" to follow an existing road than make a new one. 5. was adjusting the levels of ease for roads versus terrain height. 6. was the final version after fixing the nav point selection code for an overrun error.

So, what would random terrains look like? Here are some options.

Image

Some comments: 1 notice the river fails, I had to put in a max number of iterations otherwise the game would crash. 3 there is no existing bridge for the attackers to get across. 4 that is a really long bridge. 5 the road was unable to be found before running through the iteration cap, so some nav points may be stranded. 6 interesting to see where the weighting ends up equal and allows a split in the road.

As a final note, although it looks like the rivers all start at the same point, the start point is actually randomly selected from all the points on the top that are flat with a matching flat spot on the bottom of the map, but only using the middle 50% of the map.

Thanks.
Image
adamsderk
Site Admin
 
Posts: 1404
Joined: Tue Apr 19, 2005 11:52 pm
Location: Western Washington

Postby Ben » Wed Jun 10, 2009 10:45 pm

Those maps look pretty good, but I have a couple of quick questions for you. In the second set of images, maps 1,3,4 & 6 all show doubled up roads. Were those maps generated before the fix mentioned for map 4 of the first set of images?

Second, are you still tweaking the A* weights for your path generation? One suggestion I would have is to increase the cost for roads turning? Since in Battletech, each hexface change costs a point, I would think the roads would be as straight as possible. The curvy paths look great for the river, but not as much for the roads. This would also help the doubled roads. Also, I think it might be more tactically interesting for the roads just to plow through rough and woods instead of routing around them. This would generate some natural choke points for attackers, especially against vehicles. maybe even to the point of having woods and rough not add any extra cost to a particular hex.

Third, it looks to me like the cost for going through mountains is really high, as only one of the maps shows road on mountain. I would think tweaking that down, and maybe increasing the cost of bridges (especially the cost of bridges turning, that's not very common in real life), would stop the path finder from making real long bridges, and also less likely to hit the iteration cap.

What you've done so far certainly looks interesting though!

Thanks!
Ben
 
Posts: 169
Joined: Sat Apr 23, 2005 10:42 pm
Location: New Zealand

Postby adamsderk » Thu Jun 11, 2009 2:00 pm

Ben,

The code has already changed since I generated those images, but no, it was not before the double "road fix."

In all the discussions of A* they just say "adjust the weights." Ha, not so easy. If the weights are too light a 3 second search takes 2 minutes. If they are too heavy, they slash through illegal terrain. To make it worse, how the same weights work on different maps (i.e. different seeds) is variable (I had one map with a "t" in the road, over water, no I don't have a bridge that splits).

They will continue to be tweaked as I find maps that fail, but I don't think I will ever get it to be the best path with the minimal time I want.

As for the curvieness of the roads, that happened for two reasons. 1. this is the country, there aren't straight roads. They twist and turn around natural obstacles. 2. straight roads are made by flat land and flat land makes for a very long path generation. It is actually orders of magnitude faster to curve through bumpy terrain than run across flat terrain.

The cost of going through mountains, rough, and rivers are high. However, that doesn't keep the paths from doing it. Number 6 does above. The high cost of rivers is to keep the bridge as short as possible, but sometimes the terrain forces it longer. I actually like some of the unexpected results, it should make for some interesting battle fields :)

I'll be happy to let you have your hand at it once the version control software is running. :)

Thanks.
Image
adamsderk
Site Admin
 
Posts: 1404
Joined: Tue Apr 19, 2005 11:52 pm
Location: Western Washington

Postby Ben » Fri Jul 10, 2009 3:37 am

It's taken me some time, but I think I've finally put my finger on what didn't quite look right to me.

Shouldn't the path weight for woods and rough be the same as open ground? Since, once the roads are there, the underlying terrain doesn't affect movement costs (as long as the unit follows the road). Certainly the river cost should remain high, to keep bridges on the short side, and the elevation cost should still be there.

Anyway, I mostly wanted to post this, so I wouldn't forget about it. I'll be more then happy to look at it when you get my account set up :wink:
Ben
 
Posts: 169
Joined: Sat Apr 23, 2005 10:42 pm
Location: New Zealand

Postby adamsderk » Fri Jul 10, 2009 3:00 pm

Ben,

They are the same, the elevation differences are taken into consideration though. All of this is based on road generation. Once the roads are defined, I flatten the terrain to make the roads flat (the same as clear terrain).

I'm working on it :wink:

Thanks.
Image
adamsderk
Site Admin
 
Posts: 1404
Joined: Tue Apr 19, 2005 11:52 pm
Location: Western Washington


Return to Development Blog

Who is online

Users browsing this forum: No registered users and 1 guest

cron