A * or search the path to javascript practice
Somewhere about three or four years ago, when the amount of written, erased and again written code, on the one hand, made me an irresistible feeling of pride, but on the other (I could not see it at all), I was not going to turn into quality at all, appeared the idea of ​​implementing a browser game. How everything went and why nothing happened is a separate story, but what I learned about the path finding algorithms and how it was supposed to be put into practice I would like to share with you.
To begin with, of course, the task was set: in the game, the hero around the world should move by typing a mouse into the map, displaying the constructed path (ala Heroes of Might & Magic).
At that time, the market for browser games was several times ... not at times smaller, and a small study of this market showed that there was no decent implementation of a hero's movement map around the world (at least I did not find it). And I went to look for my own way, or rather, how to implement this way.
After searching for information about finding a path and studying it, the A * (A asterisk) algorithm was chosen as the implementation algorithm.
Here are the main advantages of this algorithm:
Describing the entire algorithm in one (yes, even two) articles is simply not possible, but for those interested, I highly recommend this translation of the article by Patrick Lester as introductory material.
After I considered that I know enough about A *, I took up the work of a real programmer - I began to search, and if someone did not implement something like that, on the platform I needed. To my great surprise, good luck turned the place I needed, and I found what I was looking for.
The workpiece, in the form of a js file, was dissected, abolished to the functions I needed, optimized, how much knowledge was enough at that time and was sentenced to perpetual service - a difficult question - where to go, where to go. Scattering ashes on my head, I regret to say that I, alas, lost all the data about who wrote the original, js version of the A * implementation, ... well, I didn’t even think that it might still be useful ... everything, hit i'm seven
')
After the main part was done, there remained some particulars - 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 css sprites. So you shouldn’t scold my code, it’s better to nastolgirovat, remembering when you wrote timidly and naively, sincerely rejoicing, when what is written, works as intended.
So:
Here's what it looks like.
And here it is all packed
There is a certain error in this particular implementation and with a certain choice of the end point there is not the shortest path, however, the search for a pattern and the solution to this problem was not justified for me in the ratio of benefit / effort and the bug was left untrained.
By the way, there used to be a skriptik for drawing obstacles, but it seems that it 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 that’s not the goal.
I really hope that at least it may be useful to someone or help, but for me writing my browser game is not for earning, but for the soul, it will probably remain a bright dream, which you always want to strive for, but which you can’t achieve.
To begin with, of course, the task was set: in the game, the hero around the world should move by typing a mouse into the map, displaying the constructed path (ala Heroes of Might & Magic).
At that time, the market for browser games was several times ... not at times smaller, and a small study of this market showed that there was no decent implementation of a hero's movement map around the world (at least I did not find it). And I went to look for my own way, or rather, how to implement this way.
After searching for information about finding a path and studying it, the A * (A asterisk) algorithm was chosen as the implementation algorithm.
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 (i.e., diagonally - this is further than in a straight line or 3 moves through the swamp is worse than 5 moves in the sand)
- You can use not only the square cells of the map, but also polygonal
- It is quite easily transformed into the Dijkstra algorithm (without a specified search vector), which makes it suitable for finding a path when the coordinates of the end point are not known.
Describing the entire algorithm in one (yes, even two) articles is simply not possible, but for those interested, I highly recommend this translation of the article by Patrick Lester as introductory material.
After I considered that I know enough about A *, I took up the work of a real programmer - I began to search, and if someone did not implement something like that, on the platform I needed. To my great surprise, good luck turned the place I needed, and I found what I was looking for.
The workpiece, in the form of a js file, was dissected, abolished to the functions I needed, optimized, how much knowledge was enough at that time and was sentenced to perpetual service - a difficult question - where to go, where to go. Scattering ashes on my head, I regret to say that I, alas, lost all the data about who wrote the original, js version of the A * implementation, ... well, I didn’t even think that it might still be useful ... everything, hit i'm seven
')
After the main part was done, there remained some particulars - 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 css sprites. So you shouldn’t scold my code, it’s better to nastolgirovat, remembering when you wrote timidly and naively, sincerely rejoicing, when what is written, works as intended.
So:
Here's what it looks like.
And here it is all packed
There is a certain error in this particular implementation and with a certain choice of the end point there is not the shortest path, however, the search for a pattern and the solution to this problem was not justified for me in the ratio of benefit / effort and the bug was left untrained.
By the way, there used to be a skriptik for drawing obstacles, but it seems that it 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 that’s not the goal.
I really hope that at least it may be useful to someone or help, but for me writing my browser game is not for earning, but for the soul, it will probably remain a bright dream, which you always want to strive for, but which you can’t achieve.
Source: https://habr.com/ru/post/54733/
All Articles