Web Arcade
2013
-Game Path Solver-
~Game Path Solver~
**This is not a game - this demonstrates the A* method used in games to find the best path to reach a location in a map.
Have you ever wondered how game characters find their way to locations? If they just went in a straight line, they would eventually get stuck on walls. Well, actually in many games they do just that! LOL
But in computer science, nearly everything has already been solved and there is a best solution available. When it comes to finding paths through obstacles, the solution is a method called A* (A-Star). Not only A* always finds a path, but assuming a valid one exists, it will also find the shortest one.
In this simulation, the character is the red circle, and you can click to tell it to go anywhere in the white area. Black blocks are walls. The character will use A* to find the shortest possible way, and also show you how many steps it took to get there. If the area cannot be reached, it will not go.
Every time you run this it will create a new random map, but you can SHIFT-CLICK to edit it anyway you like. :D
You may be asking: if A* is the best path solver, then why do my game characters sometimes end up stuck on walls? The answer to that is performance. Real time 3D games use so much computer resources just to display the 3D world that it may not be able to afford the additional processing power and memory required by A* for every single character walking in the game.
They will then use "cheaper" path finding solutions for the sake of performance, that are not as smart as A*, but will give faster (yet inaccurate) results using less processor and memory. That's how we end up with stupid game characters getting stuck running against walls! You can try all you want here - for as long as there is a viable way, it finds the best path instantly and will *NEVER* get stuck on walls. Some of the best RTS games use A* to move the troops in the game maps. ^_______^
A* finds the shortest path as fast as you can click the map, and it's flexible enough to allow you to change your mind in the middle of a path. It will then find a new path starting from where you are at the moment.
I am creating a new tank game and will use A* to drive the enemy tanks, so if they can see you, they will chase your quite efficiently. I have also used A* to drive the artificial intelligence of the monsters in my "Monster Maze" game (below), where there are as many as 50 monsters using A* at the same time in the highest level. :D
https://ken1171.deviantart.com/art/Maze-Monsters-299161958-Maze Monsters- by ken1171
This program was written in ActionScript 3.0 using freeware FlashDevelp. Hope you like it and thanks for coming by!
