Search code examples
algorithmactionscript-3mathtilesisometric

In need for an algorithm for a tile based editor

I am currently developing an tile editor for my tile based isometric engine and am currently working on the auto-tiling features.

At this point, based on the marching squares algorithm and using an bitmask, I have been able to calculate the correct corner assets to place around a tile type.

For some time I have been attempting to surround a specific tile type with an lower matching tile type. Think how the Starcraft editor(Staredit) would automatically surround an tile type with an lower matching asset.

Notice on this image from staredit how high grass is a higher asset then high dirt:

1

For example I have 3 assets ordered by their respective height. Think as the asset 3 represents a high wall, and the lower assets would represent lower walls. These assets would be placed into the metadata. 0 would represent an empty tile within the metadata.

(3,2,1)

First the 3 asset would be placed in the metadata on the location selected by the user. 

0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,3,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0

Then the 3 asset would be surrounded by the 2 asset

0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,2,2,2,0,0,0
0,0,0,2,3,2,0,0,0
0,0,0,2,2,2,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0

Finally the 2 asset would be surrounded by the 1 asset. The end result should look something like this.

0,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,0,0
0,0,1,2,2,2,1,0,0
0,0,1,2,3,2,1,0,0
0,0,1,2,2,2,1,0,0
0,0,1,1,1,1,1,0,0
0,0,0,0,0,0,0,0,0

After this process the autotiling algorithm would be executed in order to calculate the correct assets/corners for each metadata value.

Another example of this would be from this HTML5 application. Notice how the walls are the highest assets, followed by grass, then dirt and finally water. Each asset is surrounded by an lower asset. Marching Squares HTML5 Demo

I have looked into the flood fill algorithm but it seems that it does not apply to what I am trying to accomplish.

If anyone has a solution or any advice on what algorithm I should use in order to accomplish this task, please feel free to respond to this question.

The language I am using for my engine is Flash As3.

Solution

  • The best way I have found of doing this is to use BFS or Dijkstra to automatically balance the map data.