Shop Mobile More Submit  Join Login
~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

-Maze Monsters- by ken1171

This program was written in ActionScript 3.0 using freeware FlashDevelp. Hope you like it and thanks for coming by!
Add a Comment:
 
:icongraenfur:
Graenfur Featured By Owner Dec 18, 2013
Hey, about your tank collision problem: I'm not any kind of expert here and I don't know how exactly things are done in your game, but you could "record" each tanks movement in an array or something.. So when tank runs into problem like being stuck (which of course would need to be defined what is and isn't stuck) then it travels back in the recorded path until it is unstuck again..
[or the problem is exactly the detecting weather it is or isn't stuck?]
Anyway.. I dunno.. just a suggestion.
Reply
:iconken1171:
ken1171 Featured By Owner Dec 18, 2013  Professional Digital Artist
Hey, that idea might actually work! :D  The way I am doing it now is to only record the last known position before a collision has happened, and then return the tank there. But 1-step recovery is not being enough. If instead I keep an array of previous positions before a collision, there will be a better chance of recovering from getting stuck on the walls.  I can keep only, say, the last 5 positions, and then try them in reverse order until there is no more collision. I will see if that works! ^_____^
Reply
:icongraenfur:
Graenfur Featured By Owner Dec 20, 2013
I remember working with box2d and there was this 'bullet' property which could be assigned to fast objects so they would checked for collisions more often than others. While my idea is not the same, it made me figure that more detailed info about latest positions may help here.
Let me know how it works out.

Also looking forward to that game. [:
Reply
:iconken1171:
ken1171 Featured By Owner Dec 20, 2013  Professional Digital Artist
I actually solved 95% of the wall-sticking collisions with a rather simple method - just undo the last action before the collision. Simple is always better! :D  Designing levels for the game now. ^^
Reply
:icongraenfur:
Graenfur Featured By Owner Dec 21, 2013
Hmm. Isn't going backwards through recorded positions the same undoing? :D
Reply
:iconken1171:
ken1171 Featured By Owner Dec 21, 2013  Professional Digital Artist
Not really, because I only need to remember the last action before testing for collision, and if the vehicle hits something, all I have to do is to revert that action. I still have rare cases of getting stuck on the walls, but I am happy enough it's rare now.

The tanks now have better graphics, increased rate of fire, and yesterday I have completed 5 levels for the game. Just have to decide what happens when we win.
Reply
:iconratchet27:
Ratchet27 Featured By Owner Dec 8, 2013
Epic man! :)
Good ol' pathfinding. I really wish I had the time to work on programming. I feel like I could be really good at game making if I just has an extra hour each day... lol
Reply
:iconken1171:
ken1171 Featured By Owner Dec 8, 2013  Professional Digital Artist
Thank you! I am still trying to find a way to avoid getting my tank stuck on the walls because of poor collision detection. I try to pull it back to where it was right before collision, but that doesn't seem to be enough... >___<
Reply
:iconratchet27:
Ratchet27 Featured By Owner Dec 9, 2013
Oh! I've ran into that one before!
It was a while back, and I don't think I solved it...Sweating a little...  
Reply
:iconken1171:
ken1171 Featured By Owner Dec 9, 2013  Professional Digital Artist
This is a pretty common thing, so I am sure there is a solution somewhere. The problem is that my tank not only moves, but it also turns around like a real tank would move. So collision can happen even when it is just turning in place.
Reply
:iconratchet27:
Ratchet27 Featured By Owner Dec 10, 2013
Hmmm... That does seem a bit tricky. That would mean that a potential bounding box would have to rotate with the tank as well. Not only that, rotary and linear velocities must be handled by the collision detecting. I've seen this solved before via "bouncing" the tank, but that means that it literally throws the tank from the wall... I'm assuming that you are wanting nonelastic collisions... 
Reply
:iconken1171:
ken1171 Featured By Owner Dec 10, 2013  Professional Digital Artist
I have already done all that, and the tank already "bounces" off the walls after collisions, but there are certain collision angles where this causes the tank to glue to the wall instead of bouncing off. I have to look into this, but 1st, I want to finish the game. Creating the 2nd level map now. Each level has flags to capture, and after getting them all, starts appear on the map. Capturing the stars win the level.
Also have to implement player lives now. As it is now, getting killed restarts the current level indefinitely. I think I will give the players 3 lives, and maybe they can get more when winning levels.
Reply
:iconratchet27:
Ratchet27 Featured By Owner Dec 12, 2013
Ah. I see. I had a similar problem in a python pong game. If the "ball" caught the edge of the paddle, it bounced back and forth inside of the paddle. Still haven't fixed it because I built the collision methods from scratch.

That makes sense. As opposed to fixing every problem immediately and never finishing... Not that I've EVER done that... lol
Reply
:iconken1171:
ken1171 Featured By Owner Dec 12, 2013  Professional Digital Artist
Darn, this new product I have sent to the store came back from beta testing with issues I need to fix. I guess the game will have to wait a little longer.
Reply
(1 Reply)
:icony-phil:
Y-Phil Featured By Owner Dec 7, 2013  Hobbyist Digital Artist
Clap :clap: :clap: Happy Clap Cutie Emote Stare Clap clap remake 1b clap remake 1a :tinyhappyclapwithbounce: +plz :clap: :happyclap: :tardclap: :rickrollclap Clapping Emote :TheClap: Clap Clapping Emoticon 
Reply
:iconken1171:
ken1171 Featured By Owner Dec 7, 2013  Professional Digital Artist
Thank you! I am already integrating this into my tank game. It will drive the AI for simultaneous multiple enemies in the map. ^^
Reply
:icony-phil:
Y-Phil Featured By Owner Dec 7, 2013  Hobbyist Digital Artist
Cool :-)
Reply
:iconken1171:
ken1171 Featured By Owner Dec 7, 2013  Professional Digital Artist
I am currently being massacred when playing catch the flag against 2 tanks. ;p
Reply
:icony-phil:
Y-Phil Featured By Owner Dec 7, 2013  Hobbyist Digital Artist
Lol
Reply
:iconschieben:
Schieben Featured By Owner Dec 5, 2013  Hobbyist Digital Artist
Very nice! :)
Reply
:iconken1171:
ken1171 Featured By Owner Dec 5, 2013  Professional Digital Artist
Thanks! I am now integrating this into my tank game to drive the enemy units. ^^
Reply
:iconmelficexd:
melficexd Featured By Owner Dec 4, 2013  Hobbyist Digital Artist
Very interestin! :)
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Thanks! My new tank game will use A* on the enemy tank AI. ^___^
Reply
:iconkaleidobot:
Kaleidobot Featured By Owner Dec 4, 2013  Hobbyist Digital Artist
464, is that a record?
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Probably is on this 30x30 grid! :XD:
Did you edit the map to make it THAT hard to find a path? ;p
Reply
:iconkaleidobot:
Kaleidobot Featured By Owner Dec 4, 2013  Hobbyist Digital Artist
Yeah a nifty zig-zag pattern.
I think it should be possible to score even higher, but I am not a mathematician :P
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
I can think of a number of games that can be build over this grid - either to help it reach the other side, or to keep it from doing it. For example, "Pipe Dream" can easily be adapted into a grid to make the water find a pipe path to the other side. That would be fairly simple! Every time the player rotates a pipe segment, I can adjust the grid map to present the water-passable ways. Now add a timer and you have a game! :D
Reply
:iconkaleidobot:
Kaleidobot Featured By Owner Dec 5, 2013  Hobbyist Digital Artist
I agree, it's bath time for one of your characters ;)
Reply
:iconken1171:
ken1171 Featured By Owner Dec 5, 2013  Professional Digital Artist
Hmmm.... more ideas are cooking now... :D
Reply
:icongoodkittynyanchan:
GoodKittyNyanchan Featured By Owner Dec 4, 2013  Hobbyist Writer
:iconsocute-plz: This was quite a fascinyating lesson-nya. :heart: :iconazu-nyanplz:
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Thank you! I was always amused by how my troops moved in C&C Red Alert. I just told them to move to a certain place in the map, and no matter how cluttered the map was, they always got there. Now it doesn't look like magic anymore. LOL
Reply
:iconnathaniel2k:
nathaniel2k Featured By Owner Dec 11, 2013
magic doesnt stop being magic just cause you know how its done
Reply
:iconken1171:
ken1171 Featured By Owner Dec 11, 2013  Professional Digital Artist
I have put like 2, 4 and then 6 AI tanks in a level (A* driven), and it's interesting how they appear to work as a group when chasing me. When separated by a wall, one goes around from the top, and another decides to go down, leaving me no way to escape without confrontation with at least one of them. In reality the path they take is purely based on which one is the shortest, they are not really trying to surround me - but sometimes it appears that way. ^^

I have added AI behavior to give up chasing if I get far enough from them, where the distance is configurable. In that case they just go back to random patrols across the map. Conversely, if I get close enough to a tank, they will "see" me and start chasing again. I guess we can compare this to getting into their "visual range".

When a tank is hit, it is not destroyed. Instead, it stops moving and gets into automatic repair mode, where a red bar appears on top of it. Until repaired, it cannot move or shoot. I think this sounds more realistic than the traditional kill-disappear-respawn. As a side effect, if a tank is damaged on top of a flag you want to capture, you will have to wait until the tank starts moving again, which adds to the strategy part. ^^
Reply
:iconnathaniel2k:
nathaniel2k Featured By Owner Dec 11, 2013
naturally you dont want to shut them down when theyre in youre way either
Reply
:iconken1171:
ken1171 Featured By Owner Dec 11, 2013  Professional Digital Artist
Sometimes you won't have much choice. Tanks are rather slow, so you may have to shoot them if you can't outrun them. In my version of this game, shooting only buys you some time, since the tanks cannot be destroyed. But if YOU get shot, you will have to restart the level from the beginning, so things can get tense. I didn't do this yet, but I am considering giving the player about 3 lives before they game goes back to the main menu.
Reply
:iconnathaniel2k:
nathaniel2k Featured By Owner Dec 11, 2013
or you could amp up the difficulty and let them have infinite
Reply
:iconken1171:
ken1171 Featured By Owner Dec 11, 2013  Professional Digital Artist
The game levels are designed by hand, so I will only have a limited number of levels. The challenge will be of different kind, though. Something in the lines of the player having to capture all the flags and level stars without being detected by the enemy. A sort of stealth tank game. Considering the enemy is very smart, avoiding detection may become the actual game challenge.
Reply
(1 Reply)
:iconscyth118:
scyth118 Featured By Owner Dec 4, 2013  Professional Interface Designer
Very cool, it's amazing what coding knowledge can help you do.

I remember learning a less efficient method of this back in school. Love the demo :D
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Thanks! The guys I was working for have 10 years experience in the gaming industry, and they advised me NOT to use A* because of the performance hit. Nonetheless, my Maze Monsters have 50 monsters at the highest level (huge grid size!), all driven by A*, and the game never slows down. Not only that, but looking at the CPU Meter gadget, it also takes almost zero CPU when calculating paths. I am sure we are using the same A* method, so I don't know what to tell them. The game worked because I didn't know it was impossible. LOL
Reply
:iconadviel:
Adviel Featured By Owner Dec 4, 2013
so how do I win?
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
This is not a game - but instead a method used in games. This might look familiar if you play FPS or RTS games, except that this method never lets the character get stuck on walls while trying to get where you want it to. ^^
Reply
:iconadviel:
Adviel Featured By Owner Dec 4, 2013
I know that, I read the description, I was just trolling you.
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Oh, you meanie! LOL :XD:
Reply
:iconrockymeows:
rockymeows Featured By Owner Dec 4, 2013
Pretty cool ^^
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Thank you! This will be the enemy AI basis for my next game. ^___^
Reply
:iconrockymeows:
rockymeows Featured By Owner Dec 4, 2013
Np X3 cool
Reply
:iconnathaniel2k:
nathaniel2k Featured By Owner Dec 4, 2013
game makers mp_grid works pretty well, though i dunno how to apply it to platformers except for floaty enemies
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
Anything that has terrain maps can benefit from A*, where isometric games are a perfect example. Even when my tank game will be plain 2D top view, I can always create a grid on top of it just for A* to work its magic. I love coding games from scratch instead of using game engines, for then I can learn how each thing is done. ^____^
Reply
:iconnathaniel2k:
nathaniel2k Featured By Owner Dec 4, 2013
i just love making games, and finding simple answers to complex problems
Reply
:iconken1171:
ken1171 Featured By Owner Dec 4, 2013  Professional Digital Artist
I think path finding is one of those things. The A* method is fairy simple, but memory usage grows with the grid size. The gaming company I was working for decided to use other less accurate methods in their games, but my "Maze Monsters" game demonstrates nothing less than 50 monsters in a giant map - ALL using A* simultaneously with no visible slowdowns. Even in this rather smaller 30x30 grid, you can see Flash calculating paths instantly in a blink of an eye. ^^
Reply
Add a Comment:
 
×
Download SWF download, 8.9 KB



Details

Submitted on
December 4, 2013
Image Size
8.9 KB
Resolution
540×600
Link
Thumb
Embed

Stats

Views
1,371 (1 today)
Favourites
22 (who?)
Comments
104
Downloads
38
×