2d path finding?

Posted on 2009-04-22
Last Modified: 2013-12-26

I need to implement some 2d pathfinding for squares on a game board. Basically I have a bunch of 'enemies', which are cows, that are 2d sprites, really just squares. The player is a single square somewhere else on the game board. The cows all want to move towards the user on every frame, but I'd like to keep to cows from overlapping one another while trying to walk towards the player (the player will be changing their position with the mouse).

I'm not sure how to get started with this. I figure I'll just iterate through all the cows, try to move towards the player's current location, but check if that move will intersect any other cows. If so, try another direction. Since this check will be done often (I guess every 10 frames or so) it will need to be fast. Is this the right way to get started, I know there are a lot of optimizations that could be done. Anyone have any papers or a general algorithm that does this?

void animationFrame()


    Cows cows;

    Player player;

    Rect rcPlayer = player.getCurrentRect();

    for (all cows) {

        Cow cow = (currentCow);

        Rect rcCow = cow.getCurrentRect();


        // We know the current position of every other

        // cow. Try to move in a direction that won't 

        // hit anyone else, but still towards the target.

        cow.setCurrentRect(moveTowards(rcPlayer, rcCow, cows));


Rect moveTowards(Rect rcTarget, Rect rcCurrent, Rects rectsToAvoid)


    return a new position that moves towards the target but 

               which does not hit any of the objects to avoid;


Open in new window

Question by:DJ_AM_Juicebox
    LVL 25

    Expert Comment

    Well, first, which path finding algorithm are you going to use?

    Could you not just remove the nodes (squares) on which all other items exist before each time you recalculate the path?
    LVL 31

    Accepted Solution


    Author Comment

    The path finding algorithm I'm going to use is undetermined, I have no idea really!

    I don't have a node grid like as in A* support. I could break the map (which is quite large) into nodes, I'm not sure how costly it will be for every cow to do the path search though for A*. I was hoping for something less CPU intense, worse results I could live with. Something like:

    // to find the cow's next location:
    1) Project line from current position to target, length is movement speed per frame, like 10 pixels.
    2) If projection line intersects any obstacle, rotate projection line by 15 degrees.
    3) If projection line intersects any obstacle, rotate projection line by -15 degrees.
    4) Keep repeating, rotating back and forth up to 180 degrees. If nothing works, just remain in-place for this frame.

    Is that less intense than A*? I don't know. I might get funky results from this too with cows walking in circles or going down dead ends.

    I don't need perfect path-finding because the cows are supposed to be dumb anyway (for my game), it's not like a RTS with military units or whatever,

    LVL 25

    Assisted Solution

    A* is a best-first algorithm, so it wouldn't be particularly intensive in your case.

    Are your nodes/squares the size of the cows? Or are they pixel-based?

    Author Comment

    The nodes would probably be pixel-based - the characters can technically move wherever they want on the game map, there are no 'tiles' that the user sees. If I made every pixel a node though, how would that still help with collision detection though, because if the cow sprites are 64x64 for example, if A* give s me a path for two cows that are one pixel apart, it's obviously going to appear the same to the user?
    LVL 31

    Expert Comment

    "If projection line intersects any obstacle"

    this operation could be more difficult and expensive than you think. I'd be inclined to overlay a grid that is fairly fine over the region and use A*  (allowing diagonal cell moves)
    LVL 11

    Assisted Solution

    It sounds to me, like superficially anyway, you're getting answers that are overly complicated for your needs.

    Your map doesn't have any walls in it, does it?  No obstacles that can block a cow's progress, except for other cows, yes?

    Pathfinding with A* on a simple grid with no obstacles will work fine, but conceptually, you need to think of each X,Y location in your grid as a node, with a distance to the next node of 1.

    Essentially, though, your problem is that while your display is in pixels, your "cows" are 64x64.

    So you need to scale the map to be a grid that isn't pixels anymore.. it'a a grid of ScreenX/CowWidth and ScreenY/CowHeight.

    So a 640x480 screen would be a grid of 10x7.5...

    That's pretty coarse... but then you can see how the algorithm might work as you intend.  Then each address in a node corresponds to pixels by multiplying the value by 64...

    After that, you can increase the resolution of the grid... say from 10x7.5 (7 or 8) to 100x75.... then your cows still overlap a bit, but at least you can still see them...

    Then you go to pixels by multiplying by 6.4 instead...

    Hope this helps,

    Author Comment

    Thanks John. I see how A* can be applied to my game, I'm just still wondering how it will run in practice. I see two potential problems:

    1) A* works by calculating a full path to the target. So every cow needs to spend time plotting a full path to the target. Since the target (the player) is moving, this computation needs to be redone pretty much any time the user moves (which will realistically be all the time).

    2) Even if the user is stationary, and the cows compute a full unchanging path to the player, don't I still need to recalculate on each frame (more or less), because as the cows move, they may have intersecting paths, and I don't want them to run into one another - therefore I need to recompute all the time, in case a cow moved into the way of another cow. The path calculated on the previous frame is only valid for 'now', not 10 frames from now.

    I doubt games recompute a full A* path for every entity on every frame, they must have some pattern to follow which lets them spread out these calculations between frames so as the game doesn't get bogged down. I'm on a mobile device so CPU and memory are limited. After reading some articles it definitely seems A* is the best general algorithm to go with though?

    LVL 53

    Assisted Solution

    Is this supposed to be practice for path finding algorithms and other AI approaches (like the suggested A*) ? If so, it might be worth putting in the time and effort to use a relatively complicated algorithm like A*.

    If not, I'd say that the approach you thought of earlier is quite sensible :

    >> // to find the cow's next location:
    >> 1) Project line from current position to target, length is movement speed per frame, like 10 pixels.
    >> 2) If projection line intersects any obstacle, rotate projection line by 15 degrees.
    >> 3) If projection line intersects any obstacle, rotate projection line by -15 degrees.
    >> 4) Keep repeating, rotating back and forth up to 180 degrees. If nothing works, just remain in-place for this frame.

    Except that I'd align everything to a grid, and change 2) and 3) to pick one of the free neighboring nodes that are roughly in the right direction.

    Cows getting "stuck" is not really a problem, because one of them will get the player before that happens generally. And in any case, the player moves around, so the direction changes for the cows too.
    LVL 11

    Expert Comment

    Actually, that's a great point Infinity08....

    If the purpose of the exercise isn't to learn pathfinding.. like an A* algorithm, then you can simply do a manhattan distance style of moving.

    Player has an X, Y location on the grid.

    A Cow has an X,Y

    DifferenceX is PlayerX - CowX
    DifferenceY is PlayerY - CowY
    XDistance is abs(DifferenceX)
    YDistance is abs(DifferenceY)

    if XDistance > YDistance
        CowDeltaX = DifferenceX/XDistance   // Always 1 or -1
        CowDeltaY = 0  // No diagonal moves allowed so only on index can chance
        CowDeltaY = DifferenceY/YDistance   // Always 1 or -1
        CowDeltaX = 0  // No diagonal moves allowed so only on index can chance

    CowX = CowX + CowDeltaX
    CowY = CowY + CowDeltaY

    That's a very simple way to get any cow to converge on the player.

    Is this more of what you're looking for?

    (Don't run this at 60hz... you'll never see what's happening!!)



    Write Comment

    Please enter a first name

    Please enter a last name

    We will never share this with anyone.

    Featured Post

    Why You Should Analyze Threat Actor TTPs

    After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

    Suggested Solutions

    Title # Comments Views Activity
    Math question / mortgage loan question 4 114
    A second problem of optics 12 101
    Adjust number proportionately 12 59
    scoresClump  challenge 31 85
    What is RenderMan: RenderMan is a not any particular piece of software. RenderMan is an industry standard, defining set of rules that any rendering software should use, to be RenderMan-compliant. Pixar's RenderMan is a flagship implementation of …
    This article seeks to propel the full implementation of geothermal power plants in Mexico as a renewable energy source.
    how to add IIS SMTP to handle application/Scanner relays into office 365.
    Excel styles will make formatting consistent and let you apply and change formatting faster. In this tutorial, you'll learn how to use Excel's built-in styles, how to modify styles, and how to create your own. You'll also learn how to use your custo…

    737 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    20 Experts available now in Live!

    Get 1:1 Help Now