Path Finding

City Construction

Before beginning a path searching problem, there must first be things to connect with paths. For this assignment we were to read in a terrain map of a habitable land area, and build a completely completely flat city on it. My city was titled AceHill.

Elevation at a certain pixel on the terrain map is represented as it's color value. White being the highest at 255 and black being the lowest at 0. For a city to be valid it must be 500 by 500 pixels, a constant elevation, and the connected land cannot have a difference in elevation over 1. The cost to build a city was determined by the pixel's elevation change multiplied by the cost map's value at that height. The cost map was built based on how often pixels were chosen to be settled.

Developing Trade Routes

After each of the cities were built, it was important to establish roads to each of the other cities. One could use A* to compute the paths to each of the cites, but because there are so many cities, it would be faster to perform Dijkstra's on the entire map and work back from each city.

For the road map on the left, the roads constructed are a single, red pixel wide. Selecting the picture should open a larger version in a separate tab to see the roads more easily. The cost map on the right is a visual representation where the cost to travel from AceHill to that pixel is 256 raised to the value in green channel plus the value in the blue channel.