How to modify A-Star or a similar algorithm to calculate movement range in a game like Fire Emblem?

Godot Version



Hello. I recently started working on making a game that’s like a Fire Emblem game, and, actually, I have done this before, but I went and factory-reset my computer without backing up my project, because I hadn’t gotten very far in my project, and I thought I would remember how I did everything. The problem is that I actually can’t, for the life of me, remember how I went about calculating which squares the player units can get to each turn. I know I used the A-Star algorithm, and modified it a tiny bit, but I can’t remember exactly how I modified it. I remember how to calculate the attack range, though, thankfully. Anyways… by any chance, have you guys ever done this before, and would you happen to know how to calculate the movement range in GDScript?

A* is mainly for when you have a particular destination in mind. In this case, I believe you want a breadth-first search (BFS) or traversal instead, since that will let you determine the shortest distance to every reachable tile. You’d probably want to stop exploring the graph once some maximum distance has been reached.

Does that help?

Hmm, I seem to be doing something wrong, but I can’t figure out what it is. Here is how I typed it up:

func BFS(G, root):
var Q =
start_cell[“explored”] = true
while len(Q) > 0:
var v = Q.pop_back()
if v[“distance”] < selected_char.movement_limit:
for w in adjacentEdges(v):
if w[“explored”] == false:
w[“explored”] = true
w[“distance”] = 1 + v[“distance”]

Oh, jeez… It turns out I was doing the algorithms correctly, and the way i was trying to get each grid cell’s neighbouring grid cell was wrong, instead. But, I remembered how to do it right.

1 Like