My Latest Distraction
Moderators: Bob the Hamster, marionline, SDHawk
I'm pretty sure I never actually "learned" A*, despite having implemented that algorithm several times over.
One thing to add is that you can give different weights to different tiles. For example, let's suppose you have a swamp tile that you can walk through, but it takes twice as long. You can assign that tile a value of +2 instead of +1 to find the fastest path. If you have diagonal walking in your game, you can support that by giving all surrounding tiles +1... but suppose your game has more freeform movement, where it takes longer to move to a diagonally adjacent tile than to move to an orthogonally adjacent tile. In that case, you can give diagonal tiles +1.6 to represent this, and so on.
Basically I love Dijkstra pathfinding and I use it for all sorts of things, only some of which involve figuring out how to get from point A to point B.
One thing to add is that you can give different weights to different tiles. For example, let's suppose you have a swamp tile that you can walk through, but it takes twice as long. You can assign that tile a value of +2 instead of +1 to find the fastest path. If you have diagonal walking in your game, you can support that by giving all surrounding tiles +1... but suppose your game has more freeform movement, where it takes longer to move to a diagonally adjacent tile than to move to an orthogonally adjacent tile. In that case, you can give diagonal tiles +1.6 to represent this, and so on.
Basically I love Dijkstra pathfinding and I use it for all sorts of things, only some of which involve figuring out how to get from point A to point B.
- Pepsi Ranger
- Liquid Metal Slime
- Posts: 1457
- Joined: Thu Nov 22, 2007 6:25 am
- Location: South Florida
Thanks for sharing A*. That does look like the best kind of algorithm for something like I'm trying to achieve. My main issue with it has to do with storing tile information. The largest map is 200x200 tiles, which means I would need up to a possible 40,000 global variables to store information about each (unrealistic, of course, as I would limit the allowable range significantly), and trying to write thousands of definitions for a single script is unappealing, and probably excessive.
The wiki shows a graph where multiple paths fan out from the source in an effort to seek the most direct line. That's closer to what I want to do (and similar to what the first version of my script did do). What I may attempt is to send out "scouting" lines like the ones in the animated graphics and note when they hit an obstacle and set checkpoints wherever the path is obviously clear. Then start the process over again from the new checkpoint. My plan for Revision 3 of the script is to terminate the path as incalculable if more than 40 checkpoints are needed to find the destination. This would prevent overflows and script lockups. The current script terminates if the path goes more than 20 tiles outside of the direct path, though that's more for my bug fixing than it is for a permanent implementation.
In regard to the wiki's formulas on A*, I may as well be studying a foreign language. I think the best bet for me is to script an A* like algorithm but without all the extra variable storage. Placing checkpoints in safe zones and drawing a straight line between them (diagonal movement included) is probably the least resource-costly method I can think of.
The other idea I thought about last night, but may scrap if it's ridiculous, is to layer obstacles with five unique border zones, or twenty if I make them border direction specific, and direct the path to seek an alternative route once it detects the first warning zone.
As you can see, this is going to be the trickiest part of the design process, since it will affect most of the movement in the game.
EDIT:
I did consider seeking paths out as a favorable option though. I just don't see myself implementing it until after I get the basic pathfinding scripts working.
The wiki shows a graph where multiple paths fan out from the source in an effort to seek the most direct line. That's closer to what I want to do (and similar to what the first version of my script did do). What I may attempt is to send out "scouting" lines like the ones in the animated graphics and note when they hit an obstacle and set checkpoints wherever the path is obviously clear. Then start the process over again from the new checkpoint. My plan for Revision 3 of the script is to terminate the path as incalculable if more than 40 checkpoints are needed to find the destination. This would prevent overflows and script lockups. The current script terminates if the path goes more than 20 tiles outside of the direct path, though that's more for my bug fixing than it is for a permanent implementation.
In regard to the wiki's formulas on A*, I may as well be studying a foreign language. I think the best bet for me is to script an A* like algorithm but without all the extra variable storage. Placing checkpoints in safe zones and drawing a straight line between them (diagonal movement included) is probably the least resource-costly method I can think of.
The other idea I thought about last night, but may scrap if it's ridiculous, is to layer obstacles with five unique border zones, or twenty if I make them border direction specific, and direct the path to seek an alternative route once it detects the first warning zone.
As you can see, this is going to be the trickiest part of the design process, since it will affect most of the movement in the game.
EDIT:
As of now, the only movement bonus will be for paths. I may slow movement down in sandpits, but it's not really the kind of game where that will matter. It will matter that the paths are utilized, but, unless something in my planning changes, that's the only one.Mogri wrote:One thing to add is that you can give different weights to different tiles. For example, let's suppose you have a swamp tile that you can walk through, but it takes twice as long. You can assign that tile a value of +2 instead of +1 to find the fastest path. If you have diagonal walking in your game, you can support that by giving all surrounding tiles +1... but suppose your game has more freeform movement, where it takes longer to move to a diagonally adjacent tile than to move to an orthogonally adjacent tile. In that case, you can give diagonal tiles +1.6 to represent this, and so on.
I did consider seeking paths out as a favorable option though. I just don't see myself implementing it until after I get the basic pathfinding scripts working.
Last edited by Pepsi Ranger on Fri Apr 04, 2014 5:49 pm, edited 1 time in total.
Place Obligatory Signature Here
- Bob the Hamster
- Lord of the Slimes
- Posts: 7658
- Joined: Tue Oct 16, 2007 2:34 pm
- Location: Hamster Republic (Ontario Enclave)
- Contact:
Rather than storing A-Star information in global variables, what about storing it in an empty map layer?
That would give you space to store a number between 0 and 255 for every tile on the map.
Of course, A-star pathfinding will suddenly get way easier to script someday in the future when we have array data variables.
When that happens I will probably just add A-star as a built-in feature :)
That would give you space to store a number between 0 and 255 for every tile on the map.
Of course, A-star pathfinding will suddenly get way easier to script someday in the future when we have array data variables.
When that happens I will probably just add A-star as a built-in feature :)
Last edited by Bob the Hamster on Fri Apr 04, 2014 5:59 pm, edited 1 time in total.
- Pepsi Ranger
- Liquid Metal Slime
- Posts: 1457
- Joined: Thu Nov 22, 2007 6:25 am
- Location: South Florida
I could probably use Layer 6 for that. I still have to implement a proper saving feature, so hopefully that won't interfere if it turns out I need a layer for that, too. I'm not entirely sure how to store numbers in a map layer, though, but I also haven't looked it up yet, so I don't want to claim total ignorance.Bob the Hamster wrote:Rather than storing A-Star information in global variables, what about storing it in an empty map layer?
That would give you space to store a number between 0 and 255 for every tile on the map.
So many decisions to make...
EDIT: Oh, I think I see what you mean. You mean to use an empty tileset and store numbers as a "read map block." Am I right? Close?
Well, if this waypoint plan gets much more complicated, I may just scrap it for the time being and then patch the game later when these arrays and built-in A-stars are included. Given how long that might take, however, I think I'll keep trying to make this work. ;) Unless, you know, you have a plan for getting arrays to us sooner.Bob the Hamster wrote:Of course, A-star pathfinding will suddenly get way easier to script someday in the future when we have array data variables.
When that happens I will probably just add A-star as a built-in feature
Last edited by Pepsi Ranger on Fri Apr 04, 2014 7:51 pm, edited 1 time in total.
Place Obligatory Signature Here
- sotrain515
- Red Slime
- Posts: 59
- Joined: Wed Dec 26, 2012 3:23 pm
Pepsi Ranger wrote:My main issue with it has to do with storing tile information. The largest map is 200x200 tiles, which means I would need up to a possible 40,000 global variables to store information about each (unrealistic, of course, as I would limit the allowable range significantly), and trying to write thousands of definitions for a single script is unappealing, and probably excessive.
Yes, as Bob says (and I mentioned in my first post), the easiest way would be to use an unused map layer (say layer 7). This has the added benefit of making testing easier since you can sub in a map layer that has "0", "1", "2", etc. drawn in for the the zeroth, first, second, etc. tiles. You'll be able to see the radiating tile values as they are being drawn.Bob the Hamster wrote:Rather than storing A-Star information in global variables, what about storing it in an empty map layer?
That would give you space to store a number between 0 and 255 for every tile on the map.
For example, if you wanted to know the value of the tile north of the hero versus your own tile, you would have:
Code: Select all
x := hero x(me)
y := hero y(me)
own_tile_value := read map block(x, y, 7)
north_tile_value := read map block(x, y--1, 7)
if(north_tile_value >> own_tile_value, or, own_tile_value == 0)then, begin
# some stuff
Code: Select all
#clear out all of layer 7 first:
for(x, 0, map length--1)do, begin
for(y, 0, map height--1)do, begin
write map block(x, y, 7, 0)
end
end
x := #get x-tile from mouse
y := #get y-tile from mouse
write map block(x, y, 7, 1)
No need for tons of declarations. At any given time I think you'd only really need five or so (for comparing the tile your guy is standing on versus each of the four adjacent tiles).
I warn you that this way lies madness. This sounds a lot like the solution I came up with when I first started thinking about monster movement in a Tactics-esque scenario and it'll actually wind up being a lot more involved than A* (or pseudo-A* as we may actually be talking about here) with a lot less payoff.Pepsi Ranger wrote:What I may attempt is to send out "scouting" lines like the ones in the animated graphics and note when they hit an obstacle and set checkpoints wherever the path is obviously clear.
I find it helpful to think of the problem in reverse, actually, and this might help you interpret those graphics differently, too: Don't think of the A* as the searcher sending out scouting lines looking for the destination, think of it as the destination sending out scouting lines (or "radiating cost tiles", as I like to think of it) looking for the hero.
Think about this case:
Code: Select all
[ ][ ][ ][ ][ ][ ][ ]
[ ][W][W][W][W][W][ ]
[ ][W][ ][D][ ][W][C]
[ ][ ][ ][ ][ ][W][ ]
[ ][W][W][W][W][W][ ]
E: Oops, I was a little late. I'll leave this stuff here, though, mostly because it took a while to write
Last edited by sotrain515 on Fri Apr 04, 2014 7:57 pm, edited 1 time in total.
This is Dijkstra's algorithm, not A*. Mogri also used Dijkstra in Phantom Tactics. As far as I know, Newbie's Together For Victory is the only OHR game to use A* (probably BMR's too? I haven't seen a description). It used slices for the priority queue, and placed slices to the map to mark the costs of each tile rather than using a map layer.sotrain515 wrote:The way mine works is to start with the x,y coordinates of the destination (in your case, where you have clicked) and then have the x,y coordinates of the searcher (in your case, your main dude). Next you radiate outward from the destination, assigning increasing values to each tile as you fan out, with obstructions being assigned no value. Do this until you've hit your dude or reached your maximum range.
Pathing from the destination to the source, or from the source to the destination are equivalent.
As you can tell from all the games which don't use it, normally you don't need A* unless you have large maps, or are doing lots of path finding. For the large maps in this game it seems you will want something faster than Dijkstra. If the maps don't have lots of dead ends and large obstacles, something simpler like you described would probably work well enough.
Last edited by TMC on Fri Apr 04, 2014 11:21 pm, edited 1 time in total.
I implemented A* in an unreleased (barely started) game. Probably dont have too much practical advice to give, besides that you can store all your weights in 1x1 px slices and easily see if your algorithm is working properly and also not tie up a map layer.
I seem to remember my implementation somehow relying on sorting the order of the slices, too, though i cant for the life of me remember why.
I could upload it now as an example, but the script is sloppy and hacked together and full of swear words, so i dont know if it would be too helpful.
I seem to remember my implementation somehow relying on sorting the order of the slices, too, though i cant for the life of me remember why.
I could upload it now as an example, but the script is sloppy and hacked together and full of swear words, so i dont know if it would be too helpful.
- Pepsi Ranger
- Liquid Metal Slime
- Posts: 1457
- Joined: Thu Nov 22, 2007 6:25 am
- Location: South Florida
Seeing not one but two threads devoted to random map generation has made me long for progress on this game again.
Here's the thing: the discussion on A* and Dijkstra and all of these crazy pathfinding algorithms has really helped me in thinking through the navigation obstacles I face. Problem is, even with the examples in front of me, I have yet to think of a sensible way to script it. From time to time, I think about this problem, wondering if today is the day I'll crack the blockade in my brain that prevents me from really understanding how best to tackle this. Yet, ten months later, I'm still frustrated with the complexity that this adds to my scripts.
What I think I need to do is to design a separate game that's meant for testing pathfinding. That way I don't have to risk wrecking this one. I haven't made any progress on it since April because of this pathfinding issue. I know that once I've cracked it, the rest of the game's design process will be quick, easy, and fun (three great ingredients to game design).
I would love to finish this someday. I really need to give that pathfinding obstacle another stab. I can't really move into other areas of design until that's been solved. The rest of the game depends on this working.
(I realize I still haven't told you guys what this game is. So, I'll give you a hint: think Tycoon. I'll give you another hint: think Civilization. Here's one more hint for the road: this is not Civilization Tycoon or Tycoon Civilization.)
Here's the thing: the discussion on A* and Dijkstra and all of these crazy pathfinding algorithms has really helped me in thinking through the navigation obstacles I face. Problem is, even with the examples in front of me, I have yet to think of a sensible way to script it. From time to time, I think about this problem, wondering if today is the day I'll crack the blockade in my brain that prevents me from really understanding how best to tackle this. Yet, ten months later, I'm still frustrated with the complexity that this adds to my scripts.
What I think I need to do is to design a separate game that's meant for testing pathfinding. That way I don't have to risk wrecking this one. I haven't made any progress on it since April because of this pathfinding issue. I know that once I've cracked it, the rest of the game's design process will be quick, easy, and fun (three great ingredients to game design).
I would love to finish this someday. I really need to give that pathfinding obstacle another stab. I can't really move into other areas of design until that's been solved. The rest of the game depends on this working.
(I realize I still haven't told you guys what this game is. So, I'll give you a hint: think Tycoon. I'll give you another hint: think Civilization. Here's one more hint for the road: this is not Civilization Tycoon or Tycoon Civilization.)
Place Obligatory Signature Here
- BMR
- Metal King Slime
- Posts: 3310
- Joined: Mon Feb 27, 2012 2:46 pm
- Location: The Philippines
- Contact:
It's not A* or Dijkstra, but <a href="http://rpg.hamsterrepublic.com/ohrrpgce ... g">this</a> has worked fairly flawlessly for my pathfinding needs thus far if you want to use it.
Being from the third world, I reserve the right to speak in the third person.
Using Editor version wip 20170527 gfx_sdl+fb music_sdl
Using Editor version wip 20170527 gfx_sdl+fb music_sdl
- BMR
- Metal King Slime
- Posts: 3310
- Joined: Mon Feb 27, 2012 2:46 pm
- Location: The Philippines
- Contact:
Ah, I see. Yeah, that is a problem. I thought he needed it for relatively shorter distances in open areas with obstacles, not in a more maze-like area. Yeah, the pathfinding would fail in that situation.
Being from the third world, I reserve the right to speak in the third person.
Using Editor version wip 20170527 gfx_sdl+fb music_sdl
Using Editor version wip 20170527 gfx_sdl+fb music_sdl
- Pepsi Ranger
- Liquid Metal Slime
- Posts: 1457
- Joined: Thu Nov 22, 2007 6:25 am
- Location: South Florida
Before you do, I want to try one more thing. I have one more idea that might work.TMC wrote:Egads, you're still stuck on that? I'll script the pathfinding for you.
Actually, I have a few ideas that should work; problem is, I don't think plotscript can do those things yet.
Ten months away does refresh the brain a bit.
Place Obligatory Signature Here