Real Software Forums

The forum for Real Studio and other Real Software products.
[ REAL Software Website | Board Index ]
It is currently Sun Aug 18, 2019 11:57 am
xojo

All times are UTC - 5 hours




Post new topic Reply to topic  [ 12 posts ] 
Author Message
 Post subject: Pathfinding tips?
PostPosted: Thu Mar 05, 2009 12:41 pm 
Offline

Joined: Thu Jan 03, 2008 11:29 am
Posts: 101
Greetings folks, I've been toying with pathfinding in a game I'm working on and after perusing the net awhile, I think I understand the theory mostly, its the application of it which is a little tricky. I don't need a super-deluxe pathfinding system, just one better than what I now do, Robby's "El cheapo" pathfinder. :)

What I do is basically have the monsters seek you 3 out of 5 times. Rnd * 5 + 1 , if 3-5, sends them to something like:
If xHim < xYou Then xHim = xHim + 1, etc. You get the idea.

If Rnd * 5 + 1 = 1 or 2, he will go completely random. So most of the time he's seeking you, but a little of the time he's randomizing to hopefully get around some barriers. In truth, this is fine for a game like, say, a star field with ships bumping around a few stars. But when it comes to a game with things like walls or (shudder!) a maze, the routine is "toast". The artificial intelligence IQ is about 5. :)

What I have in reality is a map array of integers, MAINMAP(170,170). It is composed of a bunch of numbers representing actual tile graphics on a map. Like 1-5 = grasses, 6-20 might be tree parts, houses, etc. up to 121 possible numbers, 1-121, of which about 20 or so are "blanks", where it is OK to walk. Indeed, most of the maps are blanks (grass, etc.) so my maps are not so complicated as a maze, but there's still plenty of obstacles.

So in a pathfinding system, how might my array implement this? On a small scale, say my map looked something like:
MAINMAP(10,7) in this case

OOOOOOOOOO
OOOOOWOOOO
OOOOOWOOCO
OOOOMWOOOO
OOOOOWOOOO
OOOOOOOOOO
OOOOOOOOOO

M - Monster
W - Wall
C - Me

In this case, the monster would need to either go up 3 then over 2 then zigzag a little to me, or he'd have to go
down 2, right 2 then zigzag to me.

Any ideas how a pathfinder might be implemented with an int array like my MAINMAP(170,170)? I know its a little tricky and hoping for a couple tips I can play with. Like I said, I understand the nodes, etc., theory, but not sure how to actually apply it in a 2d map system like mine.

Here's a quick link to my project where you can see some actual maps to get an idea of what kind of stuff the various characters need to find their way around.
http://web.me.com/drdungeon/Site/MAIN.html

Any tips are really appreciated! -Robert


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Thu Mar 05, 2009 1:36 pm 
Offline

Joined: Fri Jan 06, 2006 3:21 pm
Posts: 12388
Location: Portland, OR USA
You generally want to use some kind of wave flood algorithm where you start at point M and test every adjacent space. It will be in one of four states:

a) not possible (a wall or other obstacle)
b) already visited, skip it
c) empty, add it to the list, keeping the list ordered by path length
d) the target, unwind the path

You keep a list of visited spaces, sorted by the length of the path - the number of squares or steps from the starting point. For each space, you keep a reference to the previous space - the one you stepped from to get to this space. That back pointer allows you to walk the path back to the start when you reach the target. You step sequentially through the spaces on the list and test the adjacent spaces, putting any new spaces onto the list to look at later.

If you're already doing something like this, there really isn't any way to improve it. It's a simple little algorithm that is used in everything from maze running to PC board layout in a CAD system.

Tim


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Thu Mar 05, 2009 2:21 pm 
Offline

Joined: Fri Sep 30, 2005 6:55 pm
Posts: 1522
Just type pathfinding algorithm into Google and start reading up. Since you say you understand nodes already, turn your grid into a set of nodes where nodes are connected for clear areas and disconnected when a wall is between the two nodes. Then just apply any node-based pathfinding algorithm (A* or Dijkstra's, for example) and you'll be good to go.

_________________
Those who can, do. Those who can't, make excuses.


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Tue Mar 10, 2009 6:29 pm 
Offline

Joined: Thu Jan 03, 2008 11:29 am
Posts: 101
The application, or implementation, is indeed the tricky part. I have created version 1 of my little pathfinder, and, to a degree it seems to work but I may be missing some important points dealing with the A* algorithm. My implementation may be a little crude, but its a start as I am new to pathfinding and what is needed. How to store the nodes? Keep track of them, etc?

After several days I came up with my sample which is heavily remarked for anyone who wants to give it a spin and advise. Its a little like watching an android brain which mostly thinks pretty good then unexpectedly goes berserk. I believe it may be the way I'm implementing it and the things I still don't fully understand, which are all commented in the Init buttons action section.

If anyone wishes to give it a test drive its on my site. The code is brute-force in that there are no fancy classes or functions or object-oriented things. Just basic logic using arrays so I can work with it to hopefully play with and improve the code later. I don't know how to make a Mac .dmg file so I zipped this in windows as I know macs can unzip win zip files, so remember this is designed to run on a Mac.

There's the rbp file and three tiny bitmap "gems". You'll need to change the path in the Init section because I left it in my /uz4mac directory where it looks for the gems to draw the little graphic map with.

In any case, have fun! Remember this is my first attempt at a genuine pathfinder so I expect this may look a little beginner-ish, but I learned a long time ago to walk before you run. The file, pathv1.zip is the link a little to the right of my photo. Thanks to anyone playing with it and advising! -Robert

Here's my site:
http://web.me.com/drdungeon/Site/MAIN.html


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Wed Mar 11, 2009 1:58 pm 
Offline

Joined: Mon Feb 05, 2007 11:35 am
Posts: 98
While it's been a long time since I looked at the A* algorithm, it seems to me that you're not allowing the algorithm to finish pathfinding before moving your dot. It's kind of essential to let A* take a good number of steps before you start walking it, as it might need to backtrack out of a dead end.

Tim's suggestion of a flood algorithm might be best -- once flooded, you'll know how to get from any point to any other point without having to run A* for every NPC.

_________________
Regards,

Jeff Quan
jeff@jcquan.com
http://www.jcquan.com/JQportfolio
My RBGL replacement classes: http://www.jcquan.com/REALbasic


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Wed Mar 11, 2009 4:11 pm 
Offline

Joined: Fri Jan 06, 2006 3:21 pm
Posts: 12388
Location: Portland, OR USA
Actually, the algorithm I described is essentially Dijkstra's and it will need to be applied to each NPC individually.

Tim

Edit: I suppose you could improve it (and make it A*) by weighting each square based on whether it takes you closer to the target or moves you farther away.


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Thu Mar 12, 2009 11:05 am 
Offline

Joined: Thu Jan 03, 2008 11:29 am
Posts: 101
Ok - I'm working on a new version 2. Right at the beginning. This time I'm trying to do it exactly the right way. I'm basing this mostly on the article found here:

http://www.policyalmanac.org/games/aStarTutorial.htm

which is referred to over and again as I do google searches. Does it look like I'm off to the right start with these few starting lines of code? The "how to" part? Comments welcome.

node = 1
nodec = 1 // for closed list
// Add orig to open list, save orig as parent - xorig, yorig
xopen(node) = mx
yopen(node) = my

xorig = mx
yorig = my

node = node + 1
// Add surroundings to list if not a wall. Cardinal dirs only for now
If map(mx+1,my) = 0 Then
xopen(node) = mx+1
yopen(node) = my
xparent(node) = mx // the "parent" is always where he came from. So east's parent here is the orig, as are the others
yparent(node) = my
node = node + 1 // added to list so inc
End If

If map(mx-1,my) = 0 Then
xopen(node) = mx-1
yopen(node) = my
xparent(node) = mx
yparent(node) = my
node = node + 1
End If

If map(mx,my-1) = 0 Then
xopen(node) = mx
yopen(node) = my-1
xparent(node) = mx
yparent(node) = my
node = node + 1
End If

If map(mx,my+1) = 0 Then
xopen(node) = mx
yopen(node) = my+1
xparent(node) = mx
yparent(node) = my
node = node + 1
End If

// Add 1st to closed list
xclose(nodec) = mx
yclose(nodec) = my

// Elim from open list - shift it up so others are still there, including parents so they match
For n = 1 To node - 1
xopen(n) = xopen(n+1)
yopen(n) = yopen(n+1)
xparent(n) = xparent(n+1)
yparent(n) = yparent(n+1)
Next n

// Should node = node - 1 after above?




// score the saved nodes. using gs(200) b/c g already used, and f(200) and h(200)
// from the possible squares on the open list:
// gs() is the distance from one of those to the STARTING point, xorig and yorig
// h() is estimated movement cost to move from that given square on the grid to the final destination
// f() is the sum of gs() and h()

Hopefully, I have stored the start of it properly. Now figuring the scoring part and how to proceed in some sort of loop.

P.S. How do I paste actual code in here?


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Fri Apr 17, 2009 10:31 am 
Offline

Joined: Fri Sep 30, 2005 9:16 am
Posts: 761
There was an article about this very thing in RBDeveloper written by Joe Strout, the cover story in one of the earlier issues, I believe.

http://www.rbdeveloper.com


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Wed Jul 15, 2009 7:59 am 
Offline

Joined: Thu Jan 03, 2008 11:29 am
Posts: 101
I've been playing with this for awhile and am now trying to exactly implement the ideas at the
http://www.policyalmanac.org/games/aStarTutorial.htm tutorial site. The hard part is what kind of structures and variables are needed to sort this out. Here's what I have so far, with a lot of remarks.
listcount = 1 // will INC only when OK squares are added. Avoids 0's, gaps, etc.

listclosedcount = 1 // similar to above, but will be used as index for the CLOSED list


// Add 1st orig monster location (mxvir,myvir) to top of open list
xopen(listcount) = mxvir
yopen(listcount) = myvir

// G() cost - explained later. 1st square, the start, is 0
G(listcount) = 0

// Add surrounds as well - IF's redundant here, but may be needed in a loop later
// Add EAST if no wall
If map(mxvir+1,myvir) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir + 1
yopen(listcount) = myvir
xparent(listcount) = xopen(1) // each, E,W,N,S will get same parent, (1), as we begin b/c its the same starting point
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10 // We do the G's here b/c we can insure a 1:1 coorespondance to the list, East is non diagonal, so its cost is 10.
// We could just make it ten, but the rule says ADD to parent. In the beginning here, the parent's cost is 0.
End If

// Add WEST if no wall
If map(mxvir-1,myvir) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir - 1
yopen(listcount) = myvir
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10
End If

// Add NORTH if no wall
If map(mxvir,myvir-1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir
yopen(listcount) = myvir - 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10
End If

// Add SOUTH if no wall
If map(mxvir,myvir+1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir
yopen(listcount) = myvir + 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10
End If

// Add NORTHWEST if no wall
If map(mxvir-1,myvir-1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir -1
yopen(listcount) = myvir -1
xparent(listcount) = xopen(1) // each, E,W,N,S will get same parent, (1), as we begin b/c its the same starting point
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14 // diagonal cost
End If

// Add NORTHEAST if no wall
If map(mxvir+1,myvir-1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir + 1
yopen(listcount) = myvir - 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14
End If

// Add SOUTHWEST if no wall
If map(mxvir-1,myvir+1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir - 1
yopen(listcount) = myvir + 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14
End If

// Add SOUTHEAST if no wall
If map(mxvir+1,myvir+1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir + 1
yopen(listcount) = myvir + 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14
End If
// If all four sqaures were OK, listcount will now be 9. Would be less if any walls were there.



// Add begin point to closed list - xopen and yopen were assigned mxvir and myvir earlier, so we use the (1) from that
// At beginning, listclosedcount should still be 1
xclosed(listclosedcount) = xopen(1)
yclosed(listclosedcount) = yopen(1)


// Remove 1st from list by shifting list up one
For n = 1 To listcount - 1
xopen(n) = xopen(n+1)
yopen(n) = yopen(n+1)
xparent(n) = xparent(n+1) // parents must follow to align with shifted stuff in open
yparent(n) = yparent(n+1)
G(n) = G(n+1) // this too must shift as it was added when the rest was being done
Next n

// Last item can be zapped - It has been shifted up one so no doubles should be in list
xopen(listcount) = 0
yopen(listcount) = 0

listcount = listcount - 1 // Since the last item was zapped, we must knock down the count by one

// Now, EACH square around the monster must be scored according to the F = G + H formula. Since EACH square is scored, we use F(200), G(200), H(200)
// Remember 200 is just a working "number of possible nodes" value. It could be much higher later.

// We must be careful to match each square to the same index in F(n), G(n) and H(n) so we use our listcount variable b/c it should contain 1 to the last item on list

// Now H(). This is said to be an estimate of remaining distance from CURRENT square to goal, NON-diagonal, ignoring walls.



For n = 1 To listcount

// Calc horizontal and vertical distance from goal for H()
jx = Abs(xopen(n) - xgoal)
jy = Abs(yopen(n) - ygoal)

H(n) = (jx + jy) * 10 // They say "multilpy by 10" b/c we're just looking at the non-diagonals
// The n insures the cost for THIS square

F(n) = G(n) + H(n) // Cost for this square, as per article.

Next n

// Test print
Window1.EditField7.Text = Str(F(1)) // E
Window1.EditField5.Text = Str(F(2)) // W
Window1.EditField3.Text = Str(F(3)) // N
Window1.EditField9.Text = Str(F(4)) // S


Window1.EditField2.Text = Str(F(5)) // NW
Window1.EditField4.Text = Str(F(6)) // NE
Window1.EditField8.Text = Str(F(7)) // SW
Window1.EditField10.Text = Str(F(8)) // SE

Window1.EditField13.Text = Str(listcount) // SE

// Of the squares, we must now find the lowest F score one to use as our first try. It will be added to the closed list, dropped from the open.

// These few lines will definitely find lowest value & index - tested!
LoDex = 1
Lo = F(1)

For n = 2 To listcount
If F(n) < Lo Then
LoDex = n
Lo = F(n)
End If
Next n

Window1.EditField12.Text = Str(Lo) + " " + Str(LoDex)

// Add it to closed list
listclosedcount = listclosedcount + 1

xclosed(listclosedcount) = xopen(LoDex)
yclosed(listclosedcount) = yopen(LoDex)


// Elim from open: (shift everything up one from LoDex to end)
// First, save as new monst location to test shortly
mxvir = xopen(LoDex)
myvir = yopen(LoDex)

For n = LoDex To listcount - 1
xopen(n) = xopen(n+1)
yopen(n) = yopen(n+1)
xparent(n) = xparent(n+1) // parents must follow to align with shifted stuff in open
yparent(n) = yparent(n+1)
G(n) = G(n+1) // this too must shift as it was added when the rest was being done
H(n) = H(n+1)
F(n) = F(n+1)
Next n


// Now check surrounding squares for this new one, ignoring not only walls but also if on closed list

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Not sure how this next block should be implmented to continue search???

// Add EAST if no wall or no on closed list:
If map(mxvir+1,myvir) = 0 Then
// For Loop of some sort to check I guess 1 To listclosedcount?
listcount = listcount + 1
xopen(listcount) = mxvir + 1
yopen(listcount) = myvir
xparent(listcount) = xopen(1) // which parent?
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10 // which G square?

End If

// Add WEST if no wall or no on closed list:
If map(mxvir-1,myvir) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir - 1
yopen(listcount) = myvir
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10
End If

// Add NORTH if no wall or no on closed list:
If map(mxvir,myvir-1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir
yopen(listcount) = myvir - 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10
End If

// Add SOUTH if no wall or no on closed list:
If map(mxvir,myvir+1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir
yopen(listcount) = myvir + 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 10
End If

// Add NORTHWEST if no wall or no on closed list:
If map(mxvir-1,myvir-1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir -1
yopen(listcount) = myvir -1
xparent(listcount) = xopen(1) // each, E,W,N,S will get same parent, (1), as we begin b/c its the same starting point
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14 // diagonal cost
End If

// Add NORTHEAST if no wall or no on closed list:
If map(mxvir+1,myvir-1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir + 1
yopen(listcount) = myvir - 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14
End If

// Add SOUTHWEST if no wall or no on closed list:
If map(mxvir-1,myvir+1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir - 1
yopen(listcount) = myvir + 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14
End If

// Add SOUTHEAST if no wall or no on closed list:
If map(mxvir+1,myvir+1) = 0 Then
listcount = listcount + 1
xopen(listcount) = mxvir + 1
yopen(listcount) = myvir + 1
xparent(listcount) = xopen(1)
yparent(listcount) = yopen(1)
G(listcount) = G(1) + 14
End If

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Wed Jul 15, 2009 1:19 pm 
Offline
User avatar

Joined: Sat Oct 01, 2005 1:23 pm
Posts: 74
A* is a very fine algorithm -- especially for handling things like moving units in a wargame, but for a lot of cases it's actually overkill and unrealistic. A simpler option that generally produces better results is for an NPC to have a "goal" which it sets to the last known position of whatever it's chasing. If the target runs around a corner -- well is the NPC supposed to know where the target went by ESP?

Way back when we also had a lot of trouble with A* because it would deterministically find the same path for every NPC, leading to orcs "queueing up" to go through a passage.

In general, NPCs in most computer games are *too good* at some things (pathfinding and aiming in FPS games) and incredibly bad at others. I wouldn't waste too much effort on pathfinding in most cases.


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Wed Jul 15, 2009 1:53 pm 
Offline

Joined: Mon Feb 05, 2007 11:35 am
Posts: 98
Quote:
A simpler option that generally produces better results is for an NPC to have a "goal" which it sets to the last known position of whatever it's chasing. If the target runs around a corner -- well is the NPC supposed to know where the target went by ESP?


I have one modification to this that I've used -- when the player has turned the corner and the NPC is running to the last visible spot, I start leaving a breadcrumb trail behind the player that goes cold after a few seconds. When the NPC hits the trail, it follows the breadcrumbs to the end and then stops and tries to search, eventually returning to some default state.

What this looks like in practice is that the NPC tries to continue the chase even when the player is out of view, gets confused when it can't find the player, then gives up and returns to its original state (usually some sort of patrol state).

So no A*, and the player creates the pathfinding trail -- no true pathfinding necessary!

_________________
Regards,

Jeff Quan
jeff@jcquan.com
http://www.jcquan.com/JQportfolio
My RBGL replacement classes: http://www.jcquan.com/REALbasic


Top
 Profile  
Reply with quote  
 Post subject: Re: Pathfinding tips?
PostPosted: Wed Jul 15, 2009 8:23 pm 
Offline
User avatar

Joined: Sat Oct 01, 2005 1:23 pm
Posts: 74
Yes, the breadcrumb idea works very well ... and is much more "realistic".


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 12 posts ] 

All times are UTC - 5 hours


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group