A* Path Finding - GameCreators Forum

Author

Message

Fallout

21

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 17th Dec 2003 05:20

Link

Ok, been doing some reading on the A* path finding algorithm. I need it for some AI I'm working on, and it definitely offers the solution. However, it's a proper headache to implement. The theory behind it is pretty straight forward, and writing the code to facilitate it is tricky, but achievable. The only problem is, it's bloody inefficient the way I'm planning it.

So my question is, has anyone implemented A* in their program, and is there any source code available for dbpro showing its use? I'm in one of those "I can get it done, but it wont be very good" dilemmas at the moment.

Insiiiiiiiiiiiiiiiiiiiiiiiide!

Back to top

Profile PM

Dave J

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Feb 2003

Location: Secret Military Pub, Down Under

Posted: 17th Dec 2003 06:10 Edited at: 17th Dec 2003 06:11

Link

I believe IanM has some in the codebase.

http://www.thegamecreators.com/?m=codebase_view&i=604edc86c5cdb7db3d4d2681729356b0

http://www.thegamecreators.com/?m=codebase_view&i=56984d6fa64dd67ceb1e01c8d835c957

"Computers are useless they can only give you answers."

Back to top

Profile PM Email

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 17th Dec 2003 07:35

Link

I'm using IanM's in my rts. His is about as simple to use as it gets.

Back to top

Profile PM Email Website

Pheeel

21

Years of Service

User Offline

Joined: 2nd Oct 2002

Location: Cuba

Posted: 17th Dec 2003 14:06

Link

Is there an example of A* for use with a BSP?

Back to top

Profile PM

Fallout

21

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 17th Dec 2003 15:18

Link

Looks very interesting. Looking at the function declarations, I'm assuming you use it something like this (hope IanM sees this to clarrify):

(1) set up your world
(2) Use CreateSearchMap(x,y) in accordance with the size of your world
(3) Use SetSearchMap(x,y,value) and put a 1 for every tile where these is an obstacle.
(4) Use SetSearchRestrictDiagonals(Mode) to stop it using diagonal paths when the two corresponding adjacent squares are blocked (I'll need something like this).
(5) Use SearchMapAStar8(Path,StartX,StartY,FinishX,FinishY), specifying a number "path" for where you want it to store the path data. I assume you can therefore store multiple path data within the system.
(6) Use GetSearchPathX(Path,Move) and GetSearchPathY(Path,Move) to return the X and Y grid squares for each move.

One thing I'm curious about is what if I want to remake the map for a different level. Do I just reuse the CreateSearchMap command, and it'll overwrite the last level data?

Thanks for the help.

Insiiiiiiiiiiiiiiiiiiiiiiiide!

Back to top

Profile PM

Fallout

21

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 17th Dec 2003 16:13

Link

Ok, I've done as I've described above, but its not working here. I've got a search working and an object moving along the path, but it just takes the shortest route ignoring obstructions. So for the Astar8 search, it just goes diagonally straight there. This is how I'm filling the searchmap with data:

data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
   data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
   data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
   data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
   data 1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1
   data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
   data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,1,3,0,0,0,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,2,1,3,0,0,1
   data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,2,1,3,0,1
   data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,2,1,3,1
   data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,2,1,1
   data 1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,3,0,0,2,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,2,1,3,0,0,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,1,3,0,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,1,3,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1
   data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
   CreateSearchMap(19,19)
   CreateSearchPathLists(1)
   for z=20 to 1
      for x=1 to 20
         read TempMapData
         World(x,z).object = TempMapData
         SetSearchMap(x-1,z-1,TempMapData)
      next x
   next z

+ Code Snippet

   data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
   data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
   data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
   data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
   data 1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1
   data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
   data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,1,3,0,0,0,1
   data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,2,1,3,0,0,1
   data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,2,1,3,0,1
   data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,2,1,3,1
   data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,2,1,1
   data 1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,3,0,0,2,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,2,1,3,0,0,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,1,3,0,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,1,3,1
   data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1
   data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
   CreateSearchMap(19,19)
   CreateSearchPathLists(1)
   for z=20 to 1
      for x=1 to 20
         read TempMapData
         World(x,z).object = TempMapData
         SetSearchMap(x-1,z-1,TempMapData)
      next x
   next z

Does work though. Seems like the code is working fine - i.e. It's finding the shortest route, but ignoring the obstructions. So I imagine there's something wrong with the SearchMap.

Can anyone help?

Insiiiiiiiiiiiiiiiiiiiiiiiide!

Back to top

Profile PM

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 17th Dec 2003 19:50

Link

Try this

data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1
data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,1,3,0,0,0,1
data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,2,1,3,0,0,1
data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,2,1,3,0,1
data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,2,1,3,1
data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,2,1,1
data 1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,3,0,0,2,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,2,1,3,0,0,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,1,3,0,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,1,3,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1
data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

sync on
sync rate 0

CreateSearchMap(20,20)
CreateSearchPathLists(1)

for z=1 to 20
   for x=1 to 20
      read TempMapData
      SetSearchMap(x-1,z-1,TempMapData)
   next x
next z

print SearchMapAStar8(0, 1, 1, 1, 7)

for i=1 to SearchPathSize(0)
   print GetSearchPathX(0, i), "/", GetSearchPathY(0, i)
next i

sync off

wait key
end

+ Code Snippet

data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1
data 1,0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,0,0,0,1
data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
data 1,1,1,1,1,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1
data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
data 1,0,0,0,1,0,0,0,1,0,0,1,1,1,1,1,1,1,1,1
data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,1,3,0,0,0,1
data 1,0,0,0,1,0,0,0,1,0,0,1,0,0,2,1,3,0,0,1
data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,2,1,3,0,1
data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,2,1,3,1
data 1,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,0,2,1,1
data 1,0,0,0,0,0,0,0,1,1,1,1,0,0,1,3,0,0,2,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,2,1,3,0,0,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,2,1,3,0,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,1,3,1
data 1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,2,1,1
data 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

sync on
sync rate 0

CreateSearchMap(20,20)
CreateSearchPathLists(1)

for z=1 to 20
   for x=1 to 20
      read TempMapData
      SetSearchMap(x-1,z-1,TempMapData)
   next x
next z

print SearchMapAStar8(0, 1, 1, 1, 7)

for i=1 to SearchPathSize(0)
   print GetSearchPathX(0, i), "/", GetSearchPathY(0, i)
next i

sync off

wait key
end

Using your map, it prints out the path coords between 1,1 and 1,7

For free Plug-ins, source and the DBPro Interface library for Visual C++ 6 and .NET
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Fallout

21

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 17th Dec 2003 23:04

Link

Thanks for that. Some tweaks with the numbers I'm moving from and to, and the way in which the map data is entered has got it doing something. I've obviously been using the wrong values (e.g. starting from 1 instead of 0, top left being the start instead of the bottom left etc).

Are there any known issues with it btw? Still doing tests and it seems to be working fine, but then it'll cut through walls on certain routes.

Insiiiiiiiiiiiiiiiiiiiiiiiide!

Back to top

Profile PM

Fallout

21

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 17th Dec 2003 23:19

Link

Ahhh no, found it. Looks like you have to fill the map data up from position 0,0 first, rather than starting high and working down. Seems to all be fine now.

One question though. Is it possible to set up the restrict diagonals aspect of the algorithm to not allow the path to go diagonal when its adjacent to an obstacle. Look at the code for an explanation.

+ Code Snippet

O = Empty
# = Obstruction
x = Path taken
S = Start
F = Finish


Not wanted
----------

Map:    Route Taken:
OOOOO      OOxOO
OO#OO      Ox#xO
SO#OF      xO#Ox
OO#OO      OO#OO

Wanted
------

Map:    Route Taken:
OOOOO      OxxxO
OO#OO      Ox#xO
SO#OF      xO#Ox
OO#OO      OO#OO

Hopefully that made sense. If it cuts too close to the corner piece of the square, as my object moves in realtile it will overlap the wall, so when it gets to a corner, I want it to move around it.

Well done on the code btw though. Seems to be working fine now I've figured out how to set up the map data properly.

Insiiiiiiiiiiiiiiiiiiiiiiiide!

Back to top

Profile PM

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 18th Dec 2003 00:10 Edited at: 18th Dec 2003 00:10

Link

Sorry, but I'm not planning on diving back into that code any time soon. Feel free to modify the code yourself though.

There are three ways that I can think of to solve your problem:

1) Put the check into the search routine (probably by creating a new function rather than modifying the existing function). You might find that this will slow your search down though, as you will need to do this check on every cell that you visit.

2) Create a post-processing step to smooth off paths like that. Faster, because you will only be checking for the cells that you have already determined.

3) Put proximity detection and turning code into your path-following code.

For free Plug-ins, source and the DBPro Interface library for Visual C++ 6 and .NET
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Fallout

21

Years of Service

User Offline

Joined: 1st Sep 2002

Location: Basingstoke, England

Posted: 18th Dec 2003 03:06

Link

No probs! Wasn't expect you to do it for me!

Your pointers are definitely helpful ideas, so I'll give them a go. I can probably do it fairly simply:

When a diagonal move is next:
-Check the other two points that make the cube
-If one is full, then move to the opposite free space.
-Move to the original destination next move.

Should work fine. Cheers for your help. Thanks again for the code. Very helpful (if I ever get doing with this project).

Insiiiiiiiiiiiiiiiiiiiiiiiide!

Back to top

Profile PM

genius

20

Years of Service

User Offline

Joined: 16th Oct 2003

Location: Utah, USA

Posted: 18th Dec 2003 03:44

Link

Hey IanM, would you be able to whip up a quik demo with your pathfinding?

Be happy, tomorrow is another day

Back to top

Profile PM Website

Bulleyes

21

Years of Service

User Offline

Joined: 3rd Nov 2002

Location: Cyberjaya, Malaysia

Posted: 18th Dec 2003 07:06

Link

Can I change the map data at anytime via SetSearchMap(), i.e. a dynamic world, so that the next time when I call SearchMapAStar8() it will take advantage of the updated map data.

Thanks!

Bad Nose Entertainment - Where games are forged from the flames of talent and passion.

http://www.badnose.com/

Back to top

Profile PM Email Website

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 18th Dec 2003 08:43

Link

@Genius, if you download the zip file, you'll find a simple map painter program in there.

You paint blocks in with the left mouse button, clear them with the right, and place the start and end positions at the mouse position with space and return.

Each of the different searches can then be tried using F1-F6.

@Bulleyes, you can change the map whenever you want, but don't forget that this may make any paths that you have already generated invalid by blocking them

For free Plug-ins, source and the DBPro Interface library for Visual C++ 6 and .NET
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Bulleyes

21

Years of Service

User Offline

Joined: 3rd Nov 2002

Location: Cyberjaya, Malaysia

Posted: 18th Dec 2003 09:29

Link

Yup, I know that IanM. Thanks!

BTW, I am planning to extend you library to work for 3D map as well. Do you mind?

I think it wouldn't be that hard as A* on a 3D map will be basically made up by a three dimensional grids. So when deciding which adjacent node to consider next in order to reach the final destination, I will need to consider 26 adjacent nodes (3x3x3 - 1) instead of just 9 (3x3 - 1) nodes as in 2-D maps.

I think it is even possible to extend the map features to have more than just obstacles and non-obstacles. There might be something on the map called "preferred path". Let say you have a character in your game, and you want it to take the shortest route from point A to point B. But besides using the shortest route, you might want the character to use a preferred path if it doesn't make the overall path significantly longer. Say, you want the character to move from point A to point B using the shortest path, at the same time it will try to walk on brick road if possible instead of grass. Well, I made something before in 2-D by tweaking the cost value and heuristic function in my A* algorithm.

Sounds possible? Please point me out if I overlook something.

Bad Nose Entertainment - Where games are forged from the flames of talent and passion.

http://www.badnose.com/

Back to top

Profile PM Email Website

M00NSHiNE

20

Years of Service

User Offline

Joined: 4th Aug 2003

Location: England, UK

Posted: 18th Dec 2003 10:38

Link

can a more realistic method not be used, using a sort of half-life info_node point kind of system? I plan to start working on something like this soon...

ZEDWARE website coming soon... //END TRANSMISSION//

Back to top

Profile PM

Bulleyes

21

Years of Service

User Offline

Joined: 3rd Nov 2002

Location: Cyberjaya, Malaysia

Posted: 18th Dec 2003 11:19

Link

Tell me more...

Bad Nose Entertainment - Where games are forged from the flames of talent and passion.

http://www.badnose.com/

Back to top

Profile PM Email Website

M00NSHiNE

20

Years of Service

User Offline

Joined: 4th Aug 2003

Location: England, UK

Posted: 18th Dec 2003 13:07

Link

Basically, when a HL level was made the designer placed a load of points around obstacles that the enemies used to navigate round them, rather than using more conventional pathfinding techniques such as A*. Maybe if it was crossed with a kind of A* search it could provide interesting results...

ZEDWARE website coming soon... //END TRANSMISSION//

Back to top

Profile PM

Bulleyes

21

Years of Service

User Offline

Joined: 3rd Nov 2002

Location: Cyberjaya, Malaysia

Posted: 18th Dec 2003 13:50

Link

You mean the enemy will keep moving forward blindly until it step on one of those points, and it tries to navigate around the points to avoid the obstacle?

Well, if this is the case, yes, it can be use to navigate a bot through a maze or level if it need not have to use the shortest route. It will be something like, "Oh, I bump onto a wall, so I just choose any direction so long as it will get me around the obstacle."

This is not the usual case for RTS, as the player usually want to move his units from one point to another using the shortest route.

Bad Nose Entertainment - Where games are forged from the flames of talent and passion.

http://www.badnose.com/

Back to top

Profile PM Email Website

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 18th Dec 2003 14:29 Edited at: 18th Dec 2003 14:29

Link

The current system is perfect for terrains, or even for some 3D environments. For example DOOM wasn't a truly 3D environment. It just had varying heights of ground level.

I can see some problems with extending the current library into the 3rd dimension. How do you represent a ramp?

If I were going to put together pathing for a truely 3D environment, I probably wouldn't use the library I've posted, because it really isn't designed for it.

Instead of using a grid and blocking cells, I'd create a cell/waypoint and link it to all other nearby cells (and probably provide a distance/cost for each link). This way would map directly to the environment that you are in, but it would take a lot of work to create all of the waypoints. A bonus would be the ability to use teleports automatically, and to provide preferred routes (by lowering the cost of those links).

This sounds pretty much like the system MOONSHINE is saying that they use in HL ...

For free Plug-ins, source and the DBPro Interface library for Visual C++ 6 and .NET
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Sorry your browser is not supported!

DarkBASIC Professional Discussion / A* Path Finding