My Latest Distraction

Make games! Discuss those games here.

Moderators: Bob the Hamster, marionline, SDHawk

User avatar
Mogri
Super Slime
Posts: 4668
Joined: Mon Oct 15, 2007 6:38 pm
Location: Austin, TX
Contact:

Post by Mogri »

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.
User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

Post by Pepsi Ranger »

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:
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.
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.

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
User avatar
Bob the Hamster
Lord of the Slimes
Posts: 7658
Joined: Tue Oct 16, 2007 2:34 pm
Location: Hamster Republic (Ontario Enclave)
Contact:

Post by Bob the Hamster »

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 :)
Last edited by Bob the Hamster on Fri Apr 04, 2014 5:59 pm, edited 1 time in total.
User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

Post by Pepsi Ranger »

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.
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.

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?
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 :)
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.
Last edited by Pepsi Ranger on Fri Apr 04, 2014 7:51 pm, edited 1 time in total.
Place Obligatory Signature Here
User avatar
sotrain515
Red Slime
Posts: 59
Joined: Wed Dec 26, 2012 3:23 pm

Post by sotrain515 »

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.
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.
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.

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
For another example, here is how your starting point might look after clicking the screen and beginning to radiate out the tiles:

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)
Not sure how to pull x/y values from mouse but you must already have that down given your current implementation.

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).
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 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.

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][ ]
You could send out scouting lines 'til the cows came home and never get from D to C.

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.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

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.
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.

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.
User avatar
shakeyair
Slime Knight
Posts: 217
Joined: Fri Jun 12, 2009 6:15 am

Post by shakeyair »

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.
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

shakeyair wrote: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.
For the priority queue.

Say, weren't you going to release scripts for pixel based movement? Or for a custom text system? :)
User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

Post by Pepsi Ranger »

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.)
Place Obligatory Signature Here
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

Egads, you're still stuck on that? I'll script the pathfinding for you.
User avatar
BMR
Metal King Slime
Posts: 3310
Joined: Mon Feb 27, 2012 2:46 pm
Location: The Philippines
Contact:

Post by BMR »

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
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

The problem is that that script will walk straight into dead ends, while it sounds like Pepsi wants something that will work over long distances with randomly generated obstacles in the way.
User avatar
BMR
Metal King Slime
Posts: 3310
Joined: Mon Feb 27, 2012 2:46 pm
Location: The Philippines
Contact:

Post by BMR »

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
User avatar
Pepsi Ranger
Liquid Metal Slime
Posts: 1457
Joined: Thu Nov 22, 2007 6:25 am
Location: South Florida

Post by Pepsi Ranger »

TMC wrote:Egads, you're still stuck on that? I'll script the pathfinding for you.
Before you do, I want to try one more thing. I have one more idea that might work.

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
TMC
Metal King Slime
Posts: 4308
Joined: Sun Apr 10, 2011 9:19 am

Post by TMC »

You know what, rather than scripting it, I'll just finally add a new script command to do A* on a grid. Waiting for arrays or objects before adding that is just unnecessary delay. Ha! You can't get [me] out of this now!
Post Reply