Intelligent A.I. Path Finding with GameSalad. Has anyone ever created an A* style path finder setup?

StormyStudioStormyStudio United KingdomMember Posts: 3,989
edited May 2014 in Working with GS (Mac)

Just reached a point in my game where I'd like to include path finding. It's not essential but it seems like an interesting challenge.

Has anyone ever had success creating a working algorithm?

Seems possible, but maths and possibly processor heavy.

Bit of light reading: :-/

http://en.wikipedia.org/wiki/Pathfinding

http://en.wikipedia.org/wiki/A*_search_algorithm

«13

Comments

  • MoikMoik Member, PRO Posts: 257

    I would wager it's possible almost for certain if you're only checking one move ahead and using an invisible pre-constructed underlying grid full of "occupied?" booleans. Focus on having the character navigate either down or sideways until at the proper X or Y, then do the other axis. On meeting an obstacle, try to move to the side one, then resume the path goal. That's how I picture doing it. The actor would get stuck constantly, but even modern triple-A games have pathing problems.

    To me, the biggest problem with using pathing AI is deciding what's shippable.

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    Definitely possible. Just seems like it may take some time to get a working setup.

    Ideally it will work out the most obvious paths first, then provide the route with the shortest distance for my game to highlight and my actors walk along.

    This graphic seems to show the theory visually.

    This looks interesting
    http://www.policyalmanac.org/games/aStarTutorial.htm

  • ycanycan Member, PRO Posts: 207
  • tylerglessnertylerglessner Member Posts: 246

    @StormyStudio‌ I love when you post threads like this! Really gets the mind going on what's possible with this tool!

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989

    Thanks @tylerglessner‌

    Pleased to see I keep the old grey matter churning...

    So much seems possible with GameSalad, (or any of the SDK's). It's just a case of making the best use of time, educating ourselves and enjoying the process.

  • Braydon_SFXBraydon_SFX Member, Sous Chef, PRO, Bowlboy Sidekick Posts: 9,271

    This is something a friend and I have been working on. Not much to show, but I know it's possible and it'll be really something when it's working ;)

  • MoikMoik Member, PRO Posts: 257
    edited May 2014

    I've started picturing something like:

    1. On Touch, accelerate toward the Y value of the destination and every gridspace increment steps taken by 1.
    2. On next collision, increment collisions by 1, and reset steps taken to 0, then accelerate toward the X value of the destination.
    3. On next collision, increment collisions by 1, and reset steps taken to 0, then accelerate toward the y value of the destination.
    4. If steps taken is greater than collisions, reset collisions to 0.
    5. If collisions is greater than 2, accelerate away from the destination's Y value until finding an X passage with open collision.
    6. On reaching the open passage, reset collisions to 0, and accelerate toward the X value of the destination.
    7. Resume the previous loop.

    Tracking the collisions and steps will let the actor know when its stuck in a corner. Then it can backtrack a bit to try again.
    Right now, when I simulate that loop by hand in MS Paint, it fails when on the same X or Y as the destination.
    The way I have the map set up, the best solution is to prefer heading to the edge of the map to find a new route. But, that feels like an erroneous way to set it.

    http://postimg.org/image/or5aurerh/

  • jonmulcahyjonmulcahy Member, Sous Chef Posts: 10,408

    i attempted to do the A* pathfinding a few years ago, but couldn't get much past the conception phase and moved on to other projects and ideas. I have a game that would be perfect for it, but could also work with a simple 'draw the path' option

  • The_Gamesalad_GuruThe_Gamesalad_Guru Member Posts: 9,922

    One tip for building AI and objects. If you move the enemy by controlling the velocity x and Y to keep collisions intact they can find their way around objects. My AI in puck it chases the puck right around the bumpers and such.

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    @The_Gamesalad_Guru . Thanks. That would definitely work for a lot of things and save some considerable work. Though for my game I'd like to be able to let the player select the destination, have the path worked out, tell them how many steps it's going to take and then let them decide if they want to go there (or check to see if they have enough steps available in the game to get there).

    @jonmulcahy‌ might be worth another shot now we have tables :-)

    After reading up on a few basic explanations of A* pathfinding, it seems like tables (arrays) should make it all possible.

    I think I'll give it a shot, no idea how good the end performance might be.

    Though hopefully by keeping my grid fairly small, 40 x 40. It should be ok (fingers crossed).

    Here's my understanding of what needs to be done. Trying to get it clear in my head as I write this.

    (Nodes is the word for the center of each square.. I keep jumping between calling them nodes and squares.)

    Edit: Might decide to number the grid squares rather than refer to them by column and row number all the time..

    Whats needed:

    Make an in game grid, 40 x 40

    Make game attributes to store (starting row and column number, target row and column number, parent row and column number).

    Make a table 'grid table' 40 x 40 (used to store values for each grid square, i.e. is it a wall.

    Manually (or with rules) mark any grid number that is a wall (unwalkable).

    Make a table 'closed nodes' to be used to keep track of good squares. (Values include, F, G, H, and parent row and column no.)

    Make a table 'open nodes' to be used to keep track of possible squares. (Values include, F, G, H, and parent row and column no..)

    Save the locations of the Start and end destination squares. (saving their row and column numbers to game attributes, plus mark them in the grid table as such).

    Add the starting node values to the 'Closed Nodes' table.

    Set the current game parent node values:

    Make the game.parent_row and game.parent_column attributes = the starting row and column numbers.

    Find first squares to search:

    Add the squares around the game.parent node to the 'open nodes table' list.

    If a square is a wall (non walkable) don't add it to the list.

    For my game, I won't allow diagonal movement, so I can ignore those too.

    Save the current game.parent values as the parent values for each of the new nodes that have just been added to the 'open nodes table' (save the values in the open nodes table).

    Work out the best path from the first lot of squares

    Then using the formula F = G + H work out the F value for each square on the open list.

    G = The cost of moving to this square, 10 per step (+ the G value of its parent).

    H = Number of steps directly to the target (ignoring walls). Again without diagonal movement. The number of steps is then multiplied by 10 (our value for each needed step).

    F = these two values added together.

    We then add the one with the least F value into the Closed Nodes table (and remove from the open list). Plus set it's row and columns values as the new game.parent row and columns values.

    Add new squares to search to the Open List Table:

    Find squares around the new parent square (ignoring walls, diagonals and ones in the closed nodes table). When adding them, add the parent square as their parent.

    Add them to the 'open nodes table'. Unless they're already on it... in which case:

    Check to see if any of them are already in the open nodes table. If they are see if the G value would be better if it was coming from the new parent than its previous one. Work out number of steps from start through current parent to square. If the value is lower than the previously saved G value, update the parent for that square for the new one, and work out its new F value (using F = G + H).

    Once the new nodes have been added to the open list.

    Choose the one with the lowest F value. If there are a few with the same value, choose the most recent one added.

    Add any more adjacent squares.

    Once the F values have been worked out for the latest squares. Again add the one with the lowest value (and current parent value) to the 'Closed nodes' table.

    Again repeat. Set the game.parent row and column attributes to the new node.

    Repeat search around square. Ignore those squares that are not useable. Work out F values. Save new nodes to open table, select one with lowest F value (if more than 1, select the most recent) move over to closed table..... repeat.

    Until the Target square is added into the Closed Nodes table.

    (Or the target is not found and the open nodes table is empty, which means the path is not possible... you're trapped!!).

    Then finding the path backwards:

    Then to find the path, you work backwards. By following each closed nodes parent value back from the target. As it works through it, it could mark each square as '1' in the grid table. Then your path could be highlighted or an actor told to interpolate to each of the grid numbers locations like way points.

    Think that's it...

    (sorry for the mammoth post... hope it makes sense to someone).

    I've still questions of my own on why this achieves the shortest path, but hard to figure out without making it first.

  • HopscotchHopscotch Member, PRO Posts: 2,782

    @StormyStudio‌ , as GS's bottleneck is the lack of fast loops, the challenge is to reduce the number of sequential iterations. Even the jump-point version of A* still creates a vast tree of possible paths to compare.

    An alternative to A* is Dijkstra, which is in itself more accurate yet vastly more time consuming.

    However, I came across a theoretical Concurrent Dijkstra algorithm which I think has potential in a GS environment. It usually only needs iterations equal to the straight distance from the goal, calculating all options along the way in parallel.

    With some optimisation this may be a suitable option in GS, calculating all the options for a point along the straight path in one code cycle.

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    @Hopscotch that does indeed look impressive, thanks for sharing. (I'd been ignoring that video when it popped up in my youtube searches).

    I might still give A* a go, if only to see if I can do it and get my head fully around it.. albeit slowly.

  • RThurmanRThurman Member, Sous Chef, PRO Posts: 2,879

    @StormyStudio‌ -- you might want to start with something simpler and then work up to A* and Dijkstra algorithms. For example a relatively simple method might be:

    1) Determine the euclidean distance from each node to the goal.  
       (Just use magnitude. Calculate them all at the beginning 
       and store the node distances in a table.)
    2) Make the start node the current node.
    3) From the current node, find which of the four adjacent nodes 
       has the smallest distance.  Make it the current node.
    5) When the current node <> the goal node.  
         Repeat step 3
    Otherwise
         Job is done!
    
  • natzuurnatzuur Member Posts: 304

    @RThurman said:
    StormyStudio‌ -- you might want to start with something simpler and then work up to A* and Dijkstra algorithms. For example a relatively simple method might be:

    1) Determine the euclidean distance from each node to the goal.  
       (Just use magnitude. Calculate them all at the beginning 
       and store the node distances in a table.)
    2) Make the start node the current node.
    3) From the current node, find which of the four adjacent nodes 
       has the smallest distance.  Make it the current node.
    5) When the current node <> the goal node.  
         Repeat step 3
    Otherwise
         Job is done!
    

    That's actually what I was thinking too, just have it probe a few nodes at a time to determine the path from each ok'd node in order.

  • Braydon_SFXBraydon_SFX Member, Sous Chef, PRO, Bowlboy Sidekick Posts: 9,271

    Interesting concepts. Seeing all of this almost makes me want to open up a "AI Pathfinder Contest" haha. Just allow anyone to come up with different ways of doing this. It is certainly intriguing.

  • cbtcbt Member Posts: 644

    @Braydon_SFX said:
    Interesting concepts. Seeing all of this almost makes me want to open up a "AI Pathfinder Contest" haha. Just allow anyone to come up with different ways of doing this. It is certainly intriguing.

    Wait for my finals, I don't want to miss this! :)

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    @RThurman said:
    StormyStudio‌ -- you might want to start with something simpler and then work up to A* and Dijkstra algorithms. For example a relatively simple method might be:

    1) Determine the euclidean distance from each node to the goal.  
       (Just use magnitude. Calculate them all at the beginning 
       and store the node distances in a table.)
    2) Make the start node the current node.
    3) From the current node, find which of the four adjacent nodes 
       has the smallest distance.  Make it the current node.
    5) When the current node <> the goal node.  
         Repeat step 3
    Otherwise
         Job is done!
    

    Thanks that does sound intriguing. I might be able to give that a go on route to trying to implement my own incarnation of A*.

    After a good 3 hours of work I've got the following:

    3 tables, 'open nodes', 'closed nodes' and 'path_grid'.

    I can move my starting point around the grid. (the red square)

    Activate the path finding. By pressing the red button, in the bottom left.

    It adds the starting node to the 'Closed nodes table'.

    It looks for the step above and below it.

    It checks these steps are not a obstacles, not off the edge of the given grid, not already in the 'open nodes' table. Then adds it to the 'Open nodes table'. (Note to self: need to have it check the closed nodes table too)

    If a square is in the open nodes table it is highlighted on the grid. (glowing blue)

    If it can't be added to the open nodes grid, my red button highlights to let me know. (Plus got a crude version of my GS table-izer working for quick table review).

    This first part is working, if the step above or below the starting node meets any of the criteria it wont be added to the 'Open nodes' table.

    Slowly slowly catchy monkey...

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    A little bit more progress.

    When a node (square) is stored in the 'closed nodes' table it now changes its image to a smiling face.

    All 4 nodes (up, down, left and right) around one central node are now checked to see if they meet the criteria and if it does it is added to the 'Open Nodes' table.

    It also works out the F value, using the A* pathing formula: F = G + H mentioned before.

    The F value is then displayed in yellow on each of the nodes squares.

    The green box is the target.

    So you can count the steps from a highlighted cell to the target. (time's the answer by 10. Then add another 10, which is the G value..(number of steps taken to get to this point on the path, which is 1 step from the start... 1 step = 10.).

    Damn confusing, and made all the harder by GameSalad Creator deciding to be a little picky over more than one thing that I'm 99% sure should work fine.

    Surprisingly interesting stuff though, and forcing me to use a variety of the table expressions a lot more. How comes there is a TableColSum but no TableRowSum ... I had to use two TableCellValues added together instead of the one expression. Not the end of the world, but I hadn't realised it was missing till now.

    .. Oh... Also tweak some bits, so I can make the grids at different ratios, before I'd settled on a square only grid 10 x 10, but now I can type in an values 3 x 22 and it all still works.

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    Next thing is to work out the quickest way to search for the lowest value in a table.

    (Find the node in the 'open nodes' table with the lowest F value.)

    Thinking:

    Loop over table:

    if 'F value' in the row is lower than the last one saved in a attribute, replace it with new value (and save grid number it relates to).

  • CodeMonkeyCodeMonkey Head Chef, Member, PRO Posts: 1,803
    edited May 2014

    Here's a quick video(sorry not good enough for the GS YouTube) of an old project I had that calculated shortest distance on a hex grid. Never had time to finish it and it doesn't include obstacles that would change the path. That would be some sort of possible beginning to a pathfinder AI.

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989
    edited May 2014

    Cheers @jonmulcahy‌

    Thanks @CodeMonkey... might be useful in the future.. I'll stick with my squares (diamonds) for now.

    Just had the first successful path drawn to the target... it's not fully working, plus had to keep clicking to make it get to the end.

    And it go very confused when it met a wall, and turned back and refused to budge...

    But it works .. badly :-)

    Hopefully fix and post a video some point over the weekend (if not tonight).

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989

    Video of it working ok:

    Yet to add rules that will update any side nodes already saved in the 'open nodes' table, if the path to them would be quicker if coming from another parent.

    Then on to add rules that copy the found path route into a table. And let an actor follow the path from start to finish...

    Also want to tweak settings and speed it up where I can.

    Then have a figure walk the path, and have rules that tell animation (png sequence) to turn the characters when they turn on the path.

  • Braydon_SFXBraydon_SFX Member, Sous Chef, PRO, Bowlboy Sidekick Posts: 9,271

    Oh my goodness that is so cool! Top notch, Stormy!

  • RThurmanRThurman Member, Sous Chef, PRO Posts: 2,879

    Go Stormy Go!

    Go Stormy Go!

    And all this because you went to the pub two nights ago?!?! What were you having?

  • MoikMoik Member, PRO Posts: 257

    My mind just exploded when I realized a Final Fantasy Tactics-style game could be made using this.

  • StormyStudioStormyStudio United KingdomMember Posts: 3,989

    Thanks peeps.

    It is strangely very satisfying just setting it up and watching it do its thing.

    Here's another video. (Sped up a bit).

    It's got a few issues, where it's not searching in quite the best way, but hopefully that'll improve once I add the remaining bits of the A* stuff.

    @RThurman ... yeah I really should go to the pub more. (Oh and the special liquid: English Ale called 'Spring Time', I'd never had it before but enjoyed a good 5 or so pints).

  • MoikMoik Member, PRO Posts: 257
    edited May 2014

    Oh interesting! Backing it up two steps to try again in the failed axis!
    Oh neat... and late in the third scene I see it (I'm going to call parallel to the bottom left X and parallel to the bottom right Y) returning to the Y path as soon as it exceeds the max distance of the failed X?
    This is looking super efficient as-is.
    I would love to see how it does in a unicursal maze.

Sign In or Register to comment.