 |
Castle Paradox
|
| View previous topic :: View next topic |
| Author |
Message |
Moogle1
Scourge of the Seas
Halloween 2006 Creativity Winner
Joined: 15 Jul 2004
Posts: 3377
Location: Seattle, WA
|
 Posted: Sat Apr 01, 2006 1:11 am Post subject: Pathfinding routine |
 |
|
With the forums back up, I guess I'll post the script here. The initial call to the script should look something like "makepathmap(x,y)" -- the third argument is 0 initially and is incremented on each recursive call.
The script creates a mapping of how many spaces from the initial location each other space, up to a threshold pathmapmax. How it is stored is not specified, but it uses the functions writeto and readfrom to do it. Ignoring the exact implementation of those functions, this is the script.
(Note: mapxmax and mapymax are also kind of pseudocode since a) I don't remember offhand the real names of those functions and b) I am kind of thinking of using an unused portion of the map to store the pathmap information.)
| Code: | script,makepathmap,x,y,d
(
if (x<<0,or,y<<0,or,x>>mapxmax,or,y>>mapymax) then (return)
writeto(x,y,d)
if (d>>pathmapmax) then (return)
#left
if ((readpassblock(x--1,y),and,eastwall)==false,and,readfrom(x--1,y)>>d+1)
then (makepathmap(x--1,y,d+1))
#right
if ((readpassblock(x+1,y),and,westwall)==false,and,readfrom(x+1,y)>>d+1)
then (makepathmap(x+1,y,d+1))
#up
if ((readpassblock(x,y--1),and,southwall)==false,and,readfrom(x,y--1)>>d+1)
then (makepathmap(x,y--1,d+1))
#down
if ((readpassblock(x,y--1),and,northwall)==false,and,readfrom(x,y--1)>>d+1)
then (makepathmap(x,y--1,d+1))
) |
I guess what I'm looking for here are optimizations. A reasonable threshold would be around 12 spaces from the initial location. The performance of this routine would depend greatly on the implementation of writeto/readfrom, I would guess. Any pointers? As I mentioned, my initial thought is to read/write to the map. This preserves variable space, which I think I'll be using quite thoroughly. Also, any optimizations on the function per se would also be helpful.
_________________
|
|
| Back to top |
|
 |
Mike Caron
Technomancer
Joined: 26 Jul 2003
Posts: 889
Location: Why do you keep asking?
|
| Posted: Sat Apr 01, 2006 4:32 am Post subject: Re: Pathfinding routine |
|
|
| Moogle1 wrote: | With the forums back up, I guess I'll post the script here. The initial call to the script should look something like "makepathmap(x,y)" -- the third argument is 0 initially and is incremented on each recursive call.
The script creates a mapping of how many spaces from the initial location each other space, up to a threshold pathmapmax. How it is stored is not specified, but it uses the functions writeto and readfrom to do it. Ignoring the exact implementation of those functions, this is the script.
(Note: mapxmax and mapymax are also kind of pseudocode since a) I don't remember offhand the real names of those functions and b) I am kind of thinking of using an unused portion of the map to store the pathmap information.)
| Code: | script,makepathmap,x,y,d
(
if (x<<0,or,y<<0,or,x>>mapxmax,or,y>>mapymax) then (return)
writeto(x,y,d)
if (d>>pathmapmax) then (return)
#left
if ((readpassblock(x--1,y),and,eastwall)==false,and,readfrom(x--1,y)>>d+1)
then (makepathmap(x--1,y,d+1))
#right
if ((readpassblock(x+1,y),and,westwall)==false,and,readfrom(x+1,y)>>d+1)
then (makepathmap(x+1,y,d+1))
#up
if ((readpassblock(x,y--1),and,southwall)==false,and,readfrom(x,y--1)>>d+1)
then (makepathmap(x,y--1,d+1))
#down
if ((readpassblock(x,y--1),and,northwall)==false,and,readfrom(x,y--1)>>d+1)
then (makepathmap(x,y--1,d+1))
) |
I guess what I'm looking for here are optimizations. A reasonable threshold would be around 12 spaces from the initial location. The performance of this routine would depend greatly on the implementation of writeto/readfrom, I would guess. Any pointers? As I mentioned, my initial thought is to read/write to the map. This preserves variable space, which I think I'll be using quite thoroughly. Also, any optimizations on the function per se would also be helpful. |
Well, first off, the script as is is an infinite loop. Return doesn't work the way you use it. It doesn't stop the script, it just sets the return value. You need to wrap the rest of the stuff in if blocks to work around this.
Also, you check the bordering wall of the 'next' tile (eg. going left, you check the right wall), but you also need to check the bordering wall of the current tile.
writeto/readfrom... Well, why not use the "A" or "B" walls to mark the path? Then, to follow the path, you do something like this:
| Code: |
script, hero follow path, who (
variable(e, last)
e:= true
last = -1
while(e) do (
if(last == -1) then (
#check the surrounding tiles for an 'A' tile (or 'B')
#set e to false if you can't find one
#set last to the direction you came from
if(read pass block (hero x(who)--1, hero y(who)), and, vehicle A) then (
walk hero (who, left, 1)
wait for hero (who)
last = right
) #and so forth
) else (
#check the surrounding tiles except for 'last'
#same as above
if(last <> right, and, (read pass block (hero x(who)--1, hero y(who)), and, vehicle A)) then (
walk hero (who, left, 1)
wait for hero (who)
last = right
) #and so forth
)
)
)
|
Sorry I didn't finish that script, I have to run now. But, you get the idea.
_________________
I stand corrected. No rivers ran blood today. At least, none that were caused by us.
Final Fantasy Q
OHR Developer BLOG
Official OHRRPGCE Wiki and FAQ |
|
| Back to top |
|
|
Moogle1
Scourge of the Seas
Halloween 2006 Creativity Winner
Joined: 15 Jul 2004
Posts: 3377
Location: Seattle, WA
|
| Posted: Sat Apr 01, 2006 8:29 am Post subject: |
|
|
It's not finding a path, it's finding all paths. I want the full pathmap so that I can reference it multiple times for multiple paths. Traversing it is not too complicated: you start from the end location and work backwards by going to an adjacent space with a lower number until you get to 0. Flip those directions around to get your path.
Didn't think about checking the walls of the current tile, but I almost never set up my maps in a way that that would be relevant (I'm not even sure I'll use anything other than the traditional 4-way wall for obstacles). It shouldn't affect performance significantly, though, so maybe I'll throw it in for usability's sake. Also, thanks for the reminder on return -- that would've had me confused for a bit.
Note that as I said before, this is hardly practical for something action-oriented, but it will produce highly accurate results in a relatively short amount of time, which is what I'm going for.
_________________
|
|
| Back to top |
|
|
Mike Caron
Technomancer
Joined: 26 Jul 2003
Posts: 889
Location: Why do you keep asking?
|
| Posted: Sat Apr 01, 2006 12:48 pm Post subject: |
|
|
I'm not sure what you mean by "the full pathmap". Granted, I know very little about path-finding, but if you mean information on what paths are possible, then you could just use the wall map. Specifically, any path is valid as long as you don't go through a wall.
_________________
I stand corrected. No rivers ran blood today. At least, none that were caused by us.
Final Fantasy Q
OHR Developer BLOG
Official OHRRPGCE Wiki and FAQ |
|
| Back to top |
|
|
Moogle1
Scourge of the Seas
Halloween 2006 Creativity Winner
Joined: 15 Jul 2004
Posts: 3377
Location: Seattle, WA
|
| Posted: Sat Apr 01, 2006 1:30 pm Post subject: |
|
|
The resulting mapping is f(x,y) = the minimal number of steps required to get from x,y to the source coordinates. In other words, the pathmap tells me the minimal number of steps between a location and any other location up to pathmapmax steps away. This is useful for a lot of things, such as comparing which of two targets is closer, and can also be used to find the path to those targets. It's generally quicker than haphazardly recursing through the map to find a minimal path and is also much more reusable.
It's not the most intuitive way to write a pathfinding algorithm, but it's the kind of thing you write after going through college as a CS major. Years of education and thousands of tuition dollars have paid off in the form of a Hamsterspeak pathfinding script. Hooray.
The wallmap alone is insufficient to find a path without further calculation. You could write a routine that, given the wallmap and start/end coordinates, returned a valid path, but I'm willing to bet it would run slower and/or return a less optimal path for any reasonably complex map.
_________________
|
|
| Back to top |
|
|
Mike Caron
Technomancer
Joined: 26 Jul 2003
Posts: 889
Location: Why do you keep asking?
|
|
| Back to top |
|
|
Mr B
Joined: 20 Mar 2003
Posts: 382
|
| Posted: Tue Apr 11, 2006 11:36 am Post subject: |
|
|
I don't really see what your script is doing... All it seems to be doing is to check if a path is valid, not if the path is optimal.
Could you use a fill routine, where each tile has an associated vector variable that points to one of its neighbor tiles? If you start at the destination and have each null-vector neighboring tile point to it, then each of those tiles' neighbors point to them, and so on, making sure that vectors don't point through walls, would that work? |
|
| Back to top |
|
|
Moogle1
Scourge of the Seas
Halloween 2006 Creativity Winner
Joined: 15 Jul 2004
Posts: 3377
Location: Seattle, WA
|
| Posted: Tue Apr 11, 2006 2:38 pm Post subject: |
|
|
It doesn't really find any optimal path, correct. But it makes it trivial and very fast to find an optimal path to anywhere from the start position. That's very useful for reasons I shouldn't have to explain, but I will anyway.
I'm planning on using it for a TRPG (FFT, etc.). It's nice for the AI to know how far away multiple targets are. It's also nice to use for the basic player movement.
The function actually is kind of like what you're describing. It's basically a recursive fill routine, but it's filling in the distance from the start tile.
_________________
|
|
| Back to top |
|
|
|
|
You can post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
