A* (A star) pathfinding in GameSalad

Asobu_GamesAsobu_Games PRO Posts: 261
edited August 2013 in Working with GS (Mac)
Hey fellow GS devs, :)

I'm in the early stages of planning a sim/management game that will require some pathfinding for automated non-playable characters in the game. The issue is that I also want to have a building element to the game that would let the player place and arrange objects that could act as obstacles for the NPC's. Ideally I want to have a pathfinding system where the characters can not only find an eventual path to their destination, but to find the most natural and efficient path.

Now one relatively easy way would be to have pre-determined 'building zones' where building is permitted and other 'path zones' where it is restricted. Think tower defence games like Kingdom Rush where you can only build in certain areas and can't block the path.

Ideally however I'd like players to be able to build anywhere (think Sim City) with NPC's that can adjust to the changing layout to find good paths. I have been reading about A* pathfinding and it is pretty daunting but I'm trying to get my head around it. My main question is if anyone has attempted this method before using GameSalad? And if so, is it too performance intenstive/memory hogging to be viable?

Thanks, Tim

Comments

  • Asobu_GamesAsobu_Games PRO Posts: 261
    Bump - Maybe I should move this out of the PRO only forums?
  • BoomshackBarryBoomshackBarry Member Posts: 712
    I've never attempted this - I'd say it's most likely doable, but I wouldn't have a clue how performance hungry it would be.

    From my (basic) understanding of path-finding algorithms the play area is usually split up in to a grid. There are then various techniques whereby either a path is calculated from the player to the endpoint, or backwards from the endpoint to the player.

    Taking the first instance, the player actor would need to assess each grid square surrounding it based on various merits (distance to target, is it moving in the right general direction) for each possible move it could make along each step of the grid. Once it's determined the right course of steps it can then follow that path.

    With dynamic level building the trouble is that the path-finding would have to constantly update to accommodate changes. Instead of the path being pre-calculated before the actor moves, maybe it would be best to calculate it on-the-fly, so that each step of the way it can assess each surrounding grid square at that moment in time. Or perhaps you'd need to pre-calculate the path initially as before, so that the actor knows which direction to initially start moving in, and then keep checking it for changes on-the-fly.

    The resolution of the grid comes in to play too obviously, the finer the grid the more natural the movement might appear, as the player will travel in smaller increments rather than giant chess board style leaps, but the performance requirements will jump up substantially with each subdivision of the grid.

    Back in the day Gamesalad might have struggled with this without the use of tables, but now it might be much quicker/more plausible. The for loop in the nightlies might also help assess each possible route quicker than was previously possible.

    I suppose if/when you manage to build a path finding algorithm it would then be a case of playing with various grid resolutions to see which fits your performance needs.

    As you can no doubt tell from above I'm no expert but it's got my brain fired up!
    Warning There was an error rendering this rich post.
  • KevinCrossKevinCross London, UKMember Posts: 1,894
    edited August 2013
    The for loop in the nightlies might also help assess each possible route quicker than was previously possible.
    Keep in mind that with the loops in the nightlies you can't nest loops so you can't easily loop through checking x and y positions in a grid. I did create a grid in the nightly with one loop, 8 high and 14 across using some basic maths and a counter which I can share later when I'm home from work if needed.
  • Asobu_GamesAsobu_Games PRO Posts: 261
    Hey, just wondering if an admin could move this out of the PRO forum area, I accidentally put it in there and it would be good to get a wider range of feedback :)

    Thanks for the feedback @BoomshackBarry and @KevinCross. It's a grid/tile based game so I was thinking of doing it with nodes as suggested. The tiles are a medium size, I'm thinking perhaps 25x25 or so for the play area. So the movement should be natural enough for my purposes.

    As for the problem of dynamic level building I figured a way to do would be to have the character do an initial pathfinding calculation, and then have an attribute that triggers a new path calculation if it detects that the player has blocked the original path.

    I think I would eventually be able to work this out, I was mainly wondering if anyone has had any luck with it before, so I could avoid spending a big chunk of time working on this if it will be too much of a memory hog to be viable anyway.
  • KevinCrossKevinCross London, UKMember Posts: 1,894
    edited August 2013
    I did it once in a PHP/JavaScript project a year or so ago using the examples shown on Wikipedia as a guide. That was quite helpful

    Good luck if you do pursue it.
  • kinzuakinzua Member Posts: 554
    edited September 2013
    I just came across this tutorial http://www.policyalmanac.org/games/aStarTutorial.htm, which i believe is the easiest to get started. Your query has certainly fired up my spirits too, along with @BoomshackBarry 's. Am trying to get down to it, but there are too many puzzle pieces to jot together. Time consuming and certainly not impossible.

    Though m a bit doubtful of the CPU usage these monsters will consume. Will have to try it out to inform correctly.
Sign In or Register to comment.

© Vanilla Keystone Theme 2025