A* Visualization

I've continued to make good progress on my game. One area that's been pretty fun is getting pieces to find a navigable path across the map. The algorithm I've used is called the A* algorithm .


A* is recursive and backtracking and as such it can be a bit tricky to debug. When I first implemented my version I made a small mistake that caused certain complex paths to be unresolved. The depth of the search and the number of backtracks made it very hard to analyze what was really going on. To help out I animated the search. As the search proceeded I drew the path being tested on the map (I added some sleep time to make it more watchable.) The results is that you can see the algorithm probing the nooks and crannies of the terrain trying to find a path from point A to B and from watching this behavior I was able to pinpoint the problem.


I'm certainly not the first to think of this, there are other examples of A* animation out there. But I like the effect so much I think I'll make it a configurable part of the game.





Comments

Post a Comment

Popular posts from this blog

Shark Crackers

The movie Jaws has been a fan favorite for 30 years. A lot has been written about the impact Jaws had on the movie making business and summer swimming habits but there's one aspect of the movie that's seldom been discussed, the impact Jaws had on the image of the saltine cracker. Before Robert Shaw's Quint, a cracker was a bland cake of baked flour only good as a surface to hold peanut butter or cheese, but not after. Quint elevated the cracker into the snack of sailors and shark hunters. What man has not wanted to calmly snap chunks of a cracker while saying the words: Y'all know me. Know how I earn a livin'. I'll catch this bird for you, but it ain't gonna be easy. Bad fish! Not like going down to the pond and chasing bluegills and tommycocks. This shark, swallow you whole. No shakin', no tenderizin', down you go. Much like the Eucharist is a symbol of Christ in the Catholic tradition, in Jaws, the cracker forms the edible representation of the
Read more

Running roughshod or ripshod

A common euphamism for political power abuse is saying someone or organization has ' run ripshod ' through the land. I was going to use the phrase myself the other day when I realized I had no idea what ripshod meant. I searched around and found many other users but no place that could define the word. This started me thinking that perhaps every example I found was just a perpetuation of a common mistake. I tried aother variations on the phrase and finnally hit upon a more common usage: run roughshod. The words roughshod and ripshod don't really sound the same but people use them in the same manner in similar contexts. Does anyone know the proper usage?
Read more

Axis, Axes, Axii?

While writing another post (it will probably follow this one) I needed to pluralize axis. None of the guesses I came up with passed the spell checker so I Googled it. The first hit I got was from a drafting company. (Interesting aside: word order matters in Google more than I realized - searching for "plural axis" didn't get the same dictionary oriented results as "axis plural") According to these folks the answer is: Grammatical Note : The plural of axis is axes. Some radical etymologists insist that the plural form of axis is axii, but that is only if there are three or more; One axis, two axes, three axii. The word axii, however, still doesn’t pass the spell checker, so perhaps getting grammar lessons from a drafting company isn’t such a great idea. More legitimate authorities simply list axes as the plural. If you do visit the above link to drafing company, can you answer me a question, what the heck are those diagrams depicting. I
Read more