Tuesday, July 1, 2014

Pathfinding on bitmap triangulation

Because large triangulated maps can be a pain to design by hand, I implemented into Daedalus an algorithm generating optimized triangulations from bitmap images. It is directly inspired by the bitmap segmentation in the Potrace algorithm.

How does-it work ?

Just give a picture made from black and white pixels to the algorithm. For example:

Then the algorithm returns to you a clean and beautiful triangulation:

Neither parameter nor configuration filling are required. Just give the bitmap and get the mesh.

However, black and white pictures are required. But we can consider the use of a threshold to easily convert gray scale and color images.

From that, I experimented with success the use of pathfinding on several triangulations generated from:
- a SNES Mario Kart circuit map
- a Doom map
- a picture of the labyrinth at Grace Cathedral
- a map of Paris created by artist Jazzberry Blue

I used Photoshop to extract properly black and white pictures from the previous maps. Then I just played with the algorithm and enjoyed the fast and accurate pathfinding implemented in Daedalus Lib.

As you can see by yourself:

No comments:

Post a Comment