A * or search path in practice javascript
Somewhere around three or four years ago, when the amount of code I wrote, erased and written again, on the one hand, caused me an irresistible feeling of pride, and on the other (I didn’t see it at all), I was not going to go into quality at all, it appeared the idea of implementing a browser game. How everything went and why nothing came of a separate story, but I would like to share with you what I learned about the search algorithms for the path and how it was supposed to be put into practice.
To begin with, the task was naturally set: in the game, the hero should move around the world in a poke of a mouse into a map, displaying the constructed path (ala Heroes of Might & Magic).
At that time, the market for browser games was at times ... not at times less and a little study of this market showed that there was no decent implementation of the map for moving a hero around the world (at least I did not find it). And I went to look for my way, or rather, how to implement this way.
After searching for information about finding the path and studying it, how the implementation algorithm was selected A * (A asterisk).
Here are the main advantages of this algorithm:
It is simply not possible to describe the entire algorithm in one (and even two) article, but for those interested, I highly recommend this translation of Patrick Lester’s article as an introduction.
After I thought that I knew enough about A *, I got down to the work of a real programmer - I began to look for whether someone had implemented something similar on the platform I needed. To my little surprise, luck did turn out to be the right place for me, and I found what I was looking for.
The blank, in the form of a js file, was prepared, abolished to the functions I needed, optimized for how much knowledge was available at that time, and was sentenced to eternal service for the difficult question - where to go, where to go. Sprinkling my head with ashes, I regret and regret that I, alas, lost all the data about who wrote that, the original version of js implementation A * ... well, I didn’t think when it might come in handy ... that's all, beat there are seven of me!
After the main part was done, particulars remained - to draw the found path. At that time, it was secondary and was implemented by the first method that came to mind.
Before showing how it all looks, I want to draw your attention to the fact that at that time, I had no idea about many useful things. Like for example css sprites. So you should not scold my code, it’s better to check it out, remembering when you wrote timidly and naively, sincerely rejoicing when what is written works as intended.
And so:
Here is how it looks
And here it is all packed up.
In this particular implementation, there is some error and with a certain choice of the end point there is no shortest way, however, the search for patterns and the solution to this problem was not justified for me in the ratio of benefit / labor and the bug was never caught.
By the way, once there was a script for drawing obstacles, but apparently, he has sunk into oblivion.
PS At the moment it works under: FF 3, IE 7, Chrome and Safari 4 (all under vista). Opera 9.64 refuses to work, but the goal is not that.
I really hope that at least it can come in handy or help, and for me writing my browser game, not for making money, but for the soul, will probably remain a bright dream, which I always want to strive for, but which I cannot achieve.
To begin with, the task was naturally set: in the game, the hero should move around the world in a poke of a mouse into a map, displaying the constructed path (ala Heroes of Might & Magic).
At that time, the market for browser games was at times ... not at times less and a little study of this market showed that there was no decent implementation of the map for moving a hero around the world (at least I did not find it). And I went to look for my way, or rather, how to implement this way.
After searching for information about finding the path and studying it, how the implementation algorithm was selected A * (A asterisk).
Here are the main advantages of this algorithm:
- This is one of the fastest path finding algorithms.
- You can easily manipulate the cost of the passage (that is, diagonally - it is further than a straight line or 3 moves in the swamp is worse than 5 moves in the sand)
- You can use not only square cells of the map, but also polygonal
- It can be easily transformed into the Dijkstra algorithm (without a given search vector), which makes it suitable for finding a path when the coordinates of the endpoint are not known.
It is simply not possible to describe the entire algorithm in one (and even two) article, but for those interested, I highly recommend this translation of Patrick Lester’s article as an introduction.
After I thought that I knew enough about A *, I got down to the work of a real programmer - I began to look for whether someone had implemented something similar on the platform I needed. To my little surprise, luck did turn out to be the right place for me, and I found what I was looking for.
The blank, in the form of a js file, was prepared, abolished to the functions I needed, optimized for how much knowledge was available at that time, and was sentenced to eternal service for the difficult question - where to go, where to go. Sprinkling my head with ashes, I regret and regret that I, alas, lost all the data about who wrote that, the original version of js implementation A * ... well, I didn’t think when it might come in handy ... that's all, beat there are seven of me!
After the main part was done, particulars remained - to draw the found path. At that time, it was secondary and was implemented by the first method that came to mind.
Before showing how it all looks, I want to draw your attention to the fact that at that time, I had no idea about many useful things. Like for example css sprites. So you should not scold my code, it’s better to check it out, remembering when you wrote timidly and naively, sincerely rejoicing when what is written works as intended.
And so:
Here is how it looks
And here it is all packed up.
In this particular implementation, there is some error and with a certain choice of the end point there is no shortest way, however, the search for patterns and the solution to this problem was not justified for me in the ratio of benefit / labor and the bug was never caught.
By the way, once there was a script for drawing obstacles, but apparently, he has sunk into oblivion.
PS At the moment it works under: FF 3, IE 7, Chrome and Safari 4 (all under vista). Opera 9.64 refuses to work, but the goal is not that.
I really hope that at least it can come in handy or help, and for me writing my browser game, not for making money, but for the soul, will probably remain a bright dream, which I always want to strive for, but which I cannot achieve.