Jump to content


Photo

Pathfinding


  • This topic is locked This topic is locked
374 replies to this topic

#1 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 23 October 2004 - 03:00 AM

I'm working on a few different games that require some good pathfinding. The most common application for good pathfinding would be in an RTS. What are your ideas on this subject?

Here are a few ideas to think about:

1) The popular A* algorithm is probably the most accurate and efficient pathfinding method for games that don't have many moving objects (quite rare). It will always find the shortest path to the goal (if possible). The only problem is that you have to map the grid every time an object moves, which is likely to be every step. This makes it slow and not suitable for most games. Also, it's very hard for inexperienced programmers to use.

2) Mark Overmars created a script that will move an object towards a goal while trying to avoid obstacles a while ago. It is now implemented into Game Maker as a set of functions. This method is great when there are few objects (and when they are small) but is not very accurate and will often fail or give weird results. The advantage is that it's a fast method that's easy to use. But it is not suitable for complex AI.

3. There are a few other techniques that can be used, for example the D* algorithm. There are other potential methods besides Marks. There is one that is quite reliable that I like. Basically, an object will keep a certain distance away from other objects until it meets the goal. The higher the distance between the objects, the less repulsion there is between them. When it fails, it doesn't give weird results like Mark's implementation does.

4. Another way to create effective pathfinding is to combine ideas. For example, an object may try to keep some distance away from other objects, but when it moves within a short range of obstacles it will try to use Marks potential scripts to navigate. And when the object has no other obstacles within a longer range, it might even use the A* to calculate the shortest path from start to finish.

Edited by xot, 13 April 2008 - 06:07 AM.
** Old Experts Topic **

  • 0

#2 Guest_DarkUranium_*

Guest_DarkUranium_*
  • Guests

Posted 23 October 2004 - 07:55 AM

I think I saw pathfinding in GM6 registered functions file. So if u got GM6 and it is registered, u can use that. There is download for .gm6 of that demo!

#3 bearSoft

bearSoft

    GMC Member

  • New Member
  • 1002 posts

Posted 23 October 2004 - 09:09 AM

>>D.U. ..realy :(
*sigh*

>>Ks:
i started a topic here some weeks ago. esential on the same note
http://forums.gamema...showtopic=74407
the path methods in gm all have the same weaknes -avoidence is not posible (recalkulate as u said but thats not practical so no reason to go there)

The repulsion method sound interesting!
-do u have any link or other ?? for that aproach?

hybrid solutions have the flaw that the complete solution wont be better than the individual parts offers.
at specified situations the part-selection is too problematic and will be error prone
dont like that all to mutch

Avoidence/detouring is the key problem
a good path method must not be to 'rigid' it must be posible to make some kind of 'smart' descisions even if an instance is bound to a path
'loose binding' is actually what would be needed
  • 0

#4 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 24 October 2004 - 02:38 AM

bearsoft, if you don't want rapid sprite rotations while using the potential functions then check out my RTS example in the creations forum.

I'm not looking for an extremely excelent pathfinding example, I just want something that will work without getting stuck in obvoius positions or behave weirdly under certain circumstances. Maybe I could use the A* for the terrain, and use mp_potential for individual unit collisions?
  • 0

#5 bearSoft

bearSoft

    GMC Member

  • New Member
  • 1002 posts

Posted 24 October 2004 - 10:08 AM

I will look at ur example!
gues u do not have anything on the 'repulsion' idea -

-----edit--------
found ur example but must admit that for the moment my pc cant run gm6 (inferior hw )
i hope to get new card in a week
thus u will have to wait for all the praise till then :)

Edited by bearSoft, 24 October 2004 - 11:27 AM.

  • 0

#6 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 25 October 2004 - 06:16 AM

Basically it works as follows. There is a "facing direction" which is the angle the the actual sprite is pointing. There is also just the direction variable, which defines the actual direction, or direction of movement. Next, the difference between the direction and the facing direction is calculated, taking into account angle wrapping and negative values (if you want the script then just ask). The difference is equal to the amount that you must add to the facing direction to get the true direction. This value is divided by 5 or some other value, and added to the facing direction. When drawing the sprite, draw it rotated to the value of the facing direction.

All of this happens every step with no slowdown.
  • 0

#7 bearSoft

bearSoft

    GMC Member

  • New Member
  • 1002 posts

Posted 25 October 2004 - 01:16 PM

ahh somehow a differensing apraoch
that is neat!
  • 0

#8 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 25 October 2004 - 01:52 PM

Alright, let's get back on subject here. Anyone know any other pathfinding techniques?
  • 0

#9 darkhitman

darkhitman

    GMC Member

  • New Member
  • 1384 posts

Posted 25 October 2004 - 08:51 PM

Perhaps the raycasting technique could be used? Mixed in with A*, it might serve as an alternative. Problem is, GM might not have the speed required...
  • 0

#10 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 25 October 2004 - 11:57 PM

Anyone know about the pathfinding behind proffessional RTSs like C+C or Starcraft? I would like to know how they did it. Most likely a modification of the A* that allows for temporary obstacles.
  • 0

#11 darkhitman

darkhitman

    GMC Member

  • New Member
  • 1384 posts

Posted 26 October 2004 - 08:44 PM

Yeah. Actually, I have a book on RTSs that lists the pathfinding techniques. I think SC uses BSP trees and A*.
  • 0

#12 Time of Death

Time of Death

    GMC Member

  • New Member
  • 213 posts

Posted 27 October 2004 - 04:02 AM

I just bought a book that goes through a lot of pathfinding techniquest, but haven't gotten much of a chance to look at it. So far the best plan I have is an actual course plotting system. It goes from point to point checking for collisions. When it finds one, it finds the two visible, alligned corners of the bounding box of the obstacle and calculates which one would be shortest to go around. It then sets arrays for the x and y of the point on the path, and sets a variable indicating the current number of points in the path relative to 1. It then uses the new point as the starting point and checks for obstacles again.

The only problem is, this method assumes that the pathfinding unit has no mass itself. It would be very hard to implement sprite height and width in this algorithm. So the player would go directly towards the corner of an obstacle, and when it gets close its sprite would overlap that corner. This presents a major complexity. So don't expect me to finish a script for this motion planning any time soon :blink:

The only access to video memory from GM is through the built-in collision checking functions. Any ideas as to how one might use precision? So far the only method I can think of is to draw the sprite, and use the draw_getpixel function to check which pixels are transparent and which are solid. But of course, this would be horrendously slow, and isn't practical.

ToD
  • 0

#13 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 27 October 2004 - 05:18 AM

So far the only method I can think of is to draw the sprite, and use the draw_getpixel function to check which pixels are transparent and which are solid.

Why would you do this? All the collision functions give you the option of using precise collision checking (if the sprite enables it).
  • 0

#14 Abyssal_Nuclei

Abyssal_Nuclei

    GMC Member

  • GMC Member
  • 1695 posts

Posted 27 October 2004 - 02:25 PM

why dont you just do what EA does, they have to have a way of doing it, and their games arent slow...
  • 0

#15 Time of Death

Time of Death

    GMC Member

  • New Member
  • 213 posts

Posted 27 October 2004 - 11:43 PM

Collision functions aren't flexible enough. They're meant for collision checking between existing objects, and nothing more. You can't specify sprites to use, either.
  • 0

#16 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 28 October 2004 - 05:37 AM

I think the collision functions are functional enough for these purposes.

why dont you just do what EA does, they have to have a way of doing it, and their games arent slow...

I guess it would help if we actually knew how EA did their pathfinding...although I don't think they're big on RTSs.
  • 0

#17 darkhitman

darkhitman

    GMC Member

  • New Member
  • 1384 posts

Posted 28 October 2004 - 11:46 AM

And EA uses raw C++, not GM.
  • 0

#18 Abyssal_Nuclei

Abyssal_Nuclei

    GMC Member

  • GMC Member
  • 1695 posts

Posted 28 October 2004 - 05:24 PM

still they have a way and you could prolly use it in GM too, but i dont know much about things like that so maybe you are right.
  • 0

#19 Time of Death

Time of Death

    GMC Member

  • New Member
  • 213 posts

Posted 29 October 2004 - 02:25 AM

I suppose I wasn't specific enough. The place_free, place_empty, and collision_point functions check whether the point is in collision with instances. So they are point-on-sprite collisions. The collision_line function is a line-on-sprite collision checking operation. Likewise with the other collision functions, only with different shapes. The only way to check for sprite-on-sprite collisions is with the built-in collision mechanism, which means you can only check it once each step, and in general allows very little flexability.
  • 0

#20 Yourself

Yourself

    The Ultimate Pronoun

  • Retired Staff
  • 7352 posts
  • Version:Unknown

Posted 29 October 2004 - 03:21 AM

You know, place_meeting will tell you if two objects collide and it does account for their sprites.
  • 0

#21 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 29 October 2004 - 03:37 AM

Maybe we could modify Mark's method (if anyone still has the script) and make it better.
  • 0

#22 BorisE

BorisE

    GMC Member

  • New Member
  • 200 posts

Posted 29 October 2004 - 12:11 PM

I did some experimentation with GML path functions. My advice is to use the built in grid function purely as a maze solver. One way to handle obstructions is to have objects mark their grid cells as occupied and clear them when they move.

I've written a simple routine to cull unwanted points from the path that the function returns. The remaining points can be used as "waypoints" to allow an object to move through a maze using a simpler move-to-point function.

See My Webpage for a demo using a grid based solution to get round a maze and potential-step to get round local obsticles.

Edited by BorisE, 30 October 2004 - 02:52 PM.

  • 0

#23 Keith

Keith

    GMC Member

  • New Member
  • 222 posts

Posted 29 October 2004 - 01:03 PM

I found a site that had tons of GM Tutorials and some of them were pathfinding. I downloaded them and they worked, some of them took a while to load tho but onyl because of complexity. They were editable, but where from GM4 so you have to get a converter available on the homepage. Let me see if I can find the site...

Edit: wow that was quick. Anyways, here it is:
http://c0029204.tripod.com/gm/tw.htm
Hope it helps

Edited by Keith, 29 October 2004 - 01:05 PM.

  • 0

#24 Pyroguy

Pyroguy

    GMC Member

  • New Member
  • 136 posts

Posted 30 October 2004 - 02:57 AM

EA uses a loose version of A* for generals, and then get more specific as certain units need to move around buildings, etc (it will calculate the distance and sizes of the buildings and such so units can move precisely between rotated buildings. or atleast i think that is what they do, because that would make the most logistical sense). The original C&C games (note, they were not EA games yet, but handled by Westwood) such as tiberian sun and red alert use direct A* pathfinding with an interesting grid system for the isometric format (if i remember from FinalSun correctly, the top left square is blue 0 and the bottom right is blue maximum, the top right is red 0 and the bottom left is red maximum). A* is by far the most efficient, and does not actually require much proccessor power if used correctly. Someone made a program a while ago called Pathblazer (or something to that extent, i no longer have the .gmd cause i wiped my harddrive due to a hacker...) that used A* GM code. Another way to manage A* is to have multiple units that are commanded to the same spot to use each others intel (which would make technical sense, because an army unit often relies on one person or one group of people as path finders) to move to the same location. This could also allow you to do a number of things, such as battle formations and tactics and so on... (sorry for the rambling). If you want a good website on A* programming, go HERE (A* programming site)
  • 0

#25 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 30 October 2004 - 06:05 AM

Do you think that we would be able to calculate a path using the A* every step? I've never really used it so I don't know how slow it is. Maybe we could calculate a path every 30 steps or something?
  • 0

#26 Pyroguy

Pyroguy

    GMC Member

  • New Member
  • 136 posts

Posted 30 October 2004 - 02:21 PM

The idea is to only calculate A* paths when you have to move. You then save the respective x and y positions of each square of the path, and use them when you want the unit to start moving. To calculate it every step would not be more efficient than calculating 40 paths in 1 step, but it would make the game look better (because of lag). If you spread them out, then the game can go through frames between each path figuring, and when all the paths are done being figured, you move the group as one; this will reduce lag "spikes" right after you move units (which looks pretty crappy on anyones game, to tell ya the truth). You could calculate one every step and not notice much lag, but it depends on proccessor speed; also, im not really sure why or how you would need to do this...

Edited by Pyroguy, 30 October 2004 - 02:24 PM.

  • 0

#27 CobraA1

CobraA1

    Logic Fanatic

  • New Member
  • 542 posts

Posted 30 October 2004 - 02:24 PM

That can be somewhat alleviated. Once the path is created, only attempt to re-calculate it if there's an obstacle. There's also ways to optimize it to check less squares.
  • 0

#28 Pyroguy

Pyroguy

    GMC Member

  • New Member
  • 136 posts

Posted 30 October 2004 - 02:27 PM

It is also useful to keep in mind Dijkstra's algorithm; it is essentially the same as A* except for the fact that there is no heauristic and only a generic target. You would use this, for example, if you command a resource gatherer to collect the nearest supplies. Another use would be to check for the closest unit to kill if there is a large battle.

Edited by Pyroguy, 30 October 2004 - 02:30 PM.

  • 0

#29 Time of Death

Time of Death

    GMC Member

  • New Member
  • 213 posts

Posted 30 October 2004 - 03:26 PM

Most commercial games use a modification of the A* algorithm. They construct a broad plan with a fairly large grid. When they get close to the target, they do finer calculations, checking for small obstacles, and dedciding exactly where to put the unit.

Also, many RTSs use grouping. They organise selected units into a formations, assign a master unit to the formation, and have the master unit do the A* calculations, while the rest follow, trying to avoid small obstacles individually.

If you do not use grouping, another thing to consider is to not have a large number of units doing global pathfinding in the same step. Instead, use a quene, and have the units that haven't yet done their pathfinding treck in the general direction of the goal until they do.
  • 0

#30 King Stephan

King Stephan

    www.gameboxsoftware.com

  • New Member
  • 734 posts

Posted 30 October 2004 - 06:10 PM

OK, so we need to calculate a path to maneuver around the terrain, and when we encounter smaller obstacles we need to avoid them (maybe using Mark's script). That makes sense. But how would we make an instance avoid small obstaces against it's normal path and then get back on the path?
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users