Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# 2d path finding?

Posted on 2009-04-22
Medium Priority
530 Views
Hi,

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?

Thanks
``````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;
}
``````
0
Question by:DJ_AM_Juicebox
• 3
• 2
• 2
• +2

LVL 25

Expert Comment

ID: 24206798
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?
0

LVL 31

Accepted Solution

GwynforWeb earned 500 total points
ID: 24206871
0

Author Comment

ID: 24206923
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,

Thanks
0

LVL 25

Assisted Solution

InteractiveMind earned 500 total points
ID: 24207052
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?
0

Author Comment

ID: 24207208
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?
0

LVL 31

Expert Comment

ID: 24207312
"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)
0

LVL 11

Assisted Solution

jgordos earned 500 total points
ID: 24209015
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.

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,
-john
-john
0

Author Comment

ID: 24209797
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?

Thanks
0

LVL 53

Assisted Solution

Infinity08 earned 500 total points
ID: 24212759
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.
0

LVL 11

Expert Comment

ID: 24214459
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
then
CowDeltaX = DifferenceX/XDistance   // Always 1 or -1
CowDeltaY = 0  // No diagonal moves allowed so only on index can chance
else
CowDeltaY = DifferenceY/YDistance   // Always 1 or -1
CowDeltaX = 0  // No diagonal moves allowed so only on index can chance
endif

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!!)

-john

0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

How to Win a Jar of Candy Corn: A Scientific Approach! I love mathematics. If you love mathematics also, you may enjoy this tip on how to use math to win your own jar of candy corn and to impress your friends. As I said, I love math, but I guâ€¦
When we purchase storage, we typically are advertised storage of 500GB, 1TB, 2TB and so on. However, when you actually install it into your computer, your 500GB HDD will actually show up as 465GB. Why? It has to do with the way people and computersâ€¦
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Although Jacob Bernoulli (1654-1705) has been credited as the creator of "Binomial Distribution Table", Gottfried Leibniz (1646-1716) did his dissertation on the subject in 1666; Leibniz you may recall is the co-inventor of "Calculus" and beat Isaacâ€¦
###### Suggested Courses
Course of the Month11 days, 12 hours left to enroll