Fire Emblem Movement

RosalinaGalaxer

  • Posts: 239
Hey,

I was wondering how exactly one could put together the "get from point A to point B with the best route possible" thing you see in Fire Emblem. Let's assume I've already got tile-based movement working, because I know where to find help for that. I could probably do it by coding every possible scenario, but there's got to be a better way to go about something like this.

Thanks!
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

NobodyX

  • *
  • Posts: 1228
I'm sure if you look up "pathfinding" you'll find tons of methods, and then you can pick one and figure out how to implement it in stencyl.

merrak

  • *
  • Posts: 2738
I have an extension that might be helpful. Coding every possible scenario ("brute force" solution) is practical if the number of scenarios is small--but usually it isn't.

RosalinaGalaxer

  • Posts: 239
*major facepalm* Of course it was pathfinding! I'm an idiot.

So I was messing around with your extension, merrak, and I got pretty far: I had a character that moved to each node of the found path, using the "Follow Path" behavior. Then I changed something, and the character doesn't move properly, and when I try to click (the way I set it up to find a path) a second time, the game crashes and gives me this:

TypeError: Error #1009: Cannot access a property or method of a null object reference.
   at AStar$/bestPath()[C:\Users\Play\AppData\Roaming\Stencyl\stencylworks\engine-extensions/ai-tools/AITools.hx:1291]
   at AITools$/findPath()[C:\Users\Play\AppData\Roaming\Stencyl\stencylworks\engine-extensions/ai-tools/AITools.hx:196]
   at MethodInfo-6382()[Source/scripts/ActorEvents_3.hx:113]
   at com.stencyl::Engine/update()[C:/Program Files (x86)/Stencyl/plaf/haxe/lib/stencyl/1,00/com/stencyl/Engine.hx:2348]
   at com.stencyl::Engine/postUpdate()[C:/Program Files (x86)/Stencyl/plaf/haxe/lib/stencyl/1,00/com/stencyl/Engine.hx:2618]
   at com.stencyl::Engine/onUpdate()[C:/Program Files (x86)/Stencyl/plaf/haxe/lib/stencyl/1,00/com/stencyl/Engine.hx:2611]

Since you made the extension, I'm going to assume that you'd be able to find out what I blew up. I'm gonna try and find a solution in the meantime.

Heh. I seem to be pretty good at breaking everything I've done with a tiny adjustment...
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

RosalinaGalaxer

  • Posts: 239
Okay, nevermind, I fixed that problem. However, I do get that error when I move the character into a corner, and then try to move again. No matter what direction I choose, I still get an error and the game freezes. Pretty sure that the only difference is the fact that the mentioned line of code in ActorEvents_3 is different, but it still refers to the same actual line, I just added code.
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

merrak

  • *
  • Posts: 2738
TypeError: Error #1009: Cannot access a property or method of a null object reference.
   at AStar$/bestPath()[C:\Users\Play\AppData\Roaming\Stencyl\stencylworks\engine-extensions/ai-tools/AITools.hx:1291]

This is line 1291:
Code: [Select]
graph.nodeAt( startRow, startCol ).g = 0;
The function nodeAt returns the node at row r, column c, or null if there is no node at that position--which would be the case here. What probably happened is your character moved onto a tile where there's no node. How that happened depends on how you constructed the graph or how you read it, but that would be where to look for the source of the problem.

I did provide a "node exists at row, col" block that you can use to check if the character is standing on a valid node before trying to find the path. That might be helpful for debugging--or at least providing a failsafe so your game doesn't crash. The autoDrawGraph block might also help you debug the graph. If it looks right then it's being read incorrectly.

RosalinaGalaxer

  • Posts: 239
I do have the graph being drawn, and it shows that the corners do have nodes. I don't have access to a computer ATM so I can't check the block thing right now.
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

RosalinaGalaxer

  • Posts: 239
Okay, I made the simple mistake of not setting the start row and column to the character's x and y center.

Now I have to figure out how to add limits, and get the "Follow Path" behavior to get off it's butt and do it's job...

How would one add limits to the distance you can move in one turn? For example, being only able to move five squares away from your current position over grass, as well as only being able to move say, two squares over a mountain tile. I'm pretty sure it has to do with "cost" but I'm not sure how to implement it.
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

merrak

  • *
  • Posts: 2738
Suppose you set the cost of an edge connecting two grass tiles to 1, and the cost of moving over an edge connecting two mountain tiles to 2.5. Then the total cost for moving five grass tiles or two mountain tiles will be the same.

To limit the movement, you can modify the follow path behavior so that it tallies the cost of each edge as it moves from tile to tile... like "action points". Once the NPC doesn't have enough action points to follow the next edge, it stops.

RosalinaGalaxer

  • Posts: 239
Hmm. That would be one way to do it...

I was hoping for a way that would be more based in the extension, because I want to display the places the character can move to, like this:



I thought if I modified the graph drawing, I might be able to do that, but if I can't set cost in the extension itself, that goes out the window. Is that the only way cost works?
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

merrak

  • *
  • Posts: 2738
Here's a thought. Let's suppose your character gets 5 action points and the minimum cost to move is 1. Then you know that it'll be impossible for the character to move outside of a circle of radius 5 under any circumstances. So what you do next is loop through all the (r,c) positions that lie in the circle and compute the cost to get from the character to the (r,c) position. This can be done by finding the path from character--(r,c) and computing the cost of the path. If the cost is <= 5 then highlight that position.

RosalinaGalaxer

  • Posts: 239
Well, you lost me. :P

I get the basic idea of what I'm supposed to be doing, but I'm really not sure about implementation. Should I specify the cost of a tile in it's data, and then check what tiles each possible path goes over to set my limit? Or am I way off?
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

merrak

  • *
  • Posts: 2738
If I remember correctly*, you can only specify the cost on an edge--not a node. Keep in mind you can't customize costs using the auto graph feature. Using auto graph, the cost to move in a cardinal direction is 1, and the cost to move diagonal is 1.414. If you want to customize costs, you'll have to create the graph manually using the 'create note' and 'create connection' blocks. AITools uses directed graphs, so be sure to set up the connection both ways i.e. node A connects to B and node B connects to A. (Although you can use one-way connections for cliffs, river currents, etc., and the A* implementation will know what to do with it)

There are a couple different ways set this up for your purposes. You could set the cost of an edge leading into a tile to be the cost of the tile itself. (Example: Consider a grass tile and mountain tile next to each other. It costs 2.5 AP to move onto the mountain tile, and 1 AP to move into the grass tile). Or, to get an undirected graph version, just set the cost both ways to the average cost of each tile.

Setting the cost of a tile is a good idea. Here's one approach you can use.

Code: [Select]
make a new graph

// Setting up the nodes
for each row r
    for each column c
        if a tile exists at r, c, then
            create a node at r, c
        end if
    end for
end for

// Setting up the connections
for each row r in 0...scene height (in tiles)
    for each column c in 0...scene width (in tiles)
        if a tile doesn't exist at (r,c) then continue
        if a tile exists at (r-1,c) then
            set 'cost' to cost of tile at (r-1,c) (pulled from your tile data)
            create a connection from node r,c to node r-1,c with cost 'cost'
        end if
        if a tile exists at (r+1,c) then
            set 'cost' to cost of tile at (r+1,c) (pulled from your tile data)
            create a connection from node r,c to node r+1,c with cost 'cost'
        end if
        if a tile exists at (r,c-1) then
            set 'cost' to cost of tile at (r,c-1) (pulled from your tile data)
            create a connection from node r,c to node r,c-1 with cost 'cost'
        end if
        if a tile exists at (r,c+1) then
            set 'cost' to cost of tile at (r,c+1) (pulled from your tile data)
            create a connection from node r,c to node r,c+1 with cost 'cost'
        end if
    end for
end for

You'll have to modify my psuedo code outline to handle things like tiles that can't be walked on... e.g. use " if a tile exists at (r,c) and can be travelled" instead of " if a tile exists at (r,c)".

* I have three different versions of this extension on my computer in various configurations, so I sometimes get them mixed up.

« Last Edit: May 24, 2018, 12:21:20 pm by merrak »

RosalinaGalaxer

  • Posts: 239
I tried what you said and got some weird results. I've attached the code as well as a screenshot. There should be nodes on every one of the grass tiles, as well as the bridges. I don't know what I did wrong. It also takes ~25 seconds to load the scene, but that's sort of to be expected.
Ģ̷̓l̴̥̒͑̕͝ì̷̘͈̬͈̖̂͂̔̕t̷͔͇̯̥̬̀̽̓͜͝c̵͇̦̼̮̉̐̈́̕͝ͅͅḣ̵̡̫̞͚̐̅ͅë̶̗̦̪̖͚̜́͊̄͑s̵̺̹̖̼̥̃.̴̮̫͐ ̶̛̓̇̾̎

“I have never seen a more heated discussion about context, jazz, and cats.” - VanillaButterz

merrak

  • *
  • Posts: 2738
Hmm... there's a lot going on in your code that I can't tell if there's a problem or not. For instance, 'Row' and 'Column' appear to be lists--but do they have the correct values? You're also creating two sets of edges between every node--but then your image of your graph shows some edges aren't established at all. I don't know what to make of that. If I remember correctly, the draw graph function will draw every node first, then draw every edge--so some edges shouldn't be drawn over and hidden by nodes.

You'll need to make some significant changes anyway, because you definitely don't want the connections doubled up. It looks like I made the same mistake in my psuedo code.  :-[ I'm going to edit my previous post to fix it, but a simpler setup would be to look at the example I used in the sample project.  The relevant part is attached.

As for the nodes, you use r and c before you define them. I wouldn't assume unused number attributes default to 0. If you used r and c elsewhere, they'll start at their previous values.

« Last Edit: May 24, 2018, 12:22:55 pm by merrak »