# Tile based movement pathfinding

I’m working on a tile based, point and click movement system.

As of right now, what I have is a basic translation script for movement. the primary functionality of it is based off of identifying the relative position of a tile to the character and then doing a simple transform to it. The equation I use is this:

x1 = Starting position X
x2 = Ending position X
x3 = Translation required in X

x3 = ((x1 - x2) * -1)

This same equation works for all of the three dimensions, and it allows me to do an easy and quick transform from point to point in my tile-grid.

However, I want the character to do tile-based path-finding with no diagonals. In order to do this, what I think may work is using a loop to #1 determine which axis, X or Z (translation in Y occurs based on the tiles and by extension the terrain) has a greater amount of translation remaining to be done (The X-axis would be given extra weight by having its function work via a >= instead of just a > operator). and #2 then use a simple function to translate the character 1 tile on that axis.

How this would work, in theory, is say that I had a character moving from a tile with position (0,0,0) to a tile with position (4,0,8). In theory, the function would move along the z-axis for 4 tiles, then move once on the x-axis, then once on Z, then X, then Z, etc… till it reached its final position.

Now, I don’t want to go ahead and spend the time to script this and expect it to work until I have some constructive input from my fellows: you all. If you have any ideas or criticisms, please tell me, I need all the help I can get on this.

Sounds like you want to give A* from Aron Granberg (sturestone on the board) a look

Note that this:

x3 = ((x1 - x2) * -1)

Can simply be written as:

x3 = x2 - x1

As for your question, if there are no obstacles and you’re just wanting to adjust the way in which the agent moves to the goal, A* may be more than you need. In any case, what you described in your post sounds reasonable, and is probably what I’d try first.

Oh, lol, good call on the rewritten equation, I can’t believe I missed that.

As for obstacles, there will be some “present” so to speak in that there will simply be tiles that wont be walkable. Would A* still be viable for that?

If there are just a few obstacles here and there, you may be able to get away with a local pathfinding method (e.g. obstacle avoidance or wall-following), but for anything more involved than that, A* is probably what you want.

if there were no obstacles, you can just walk directly to your desired location, no need for path finding

the way I would try to do it is with a recursive function. You try to walk on the tile that is along the direction of your destination first. If you are going to tile 4,4 from 0,0, you try to walk to 0,1 and 1,0 first (then 0,-1 and -1,0). If you can walk on the tile (because it is not an obstacle and because you haven’t visited it yet), you call the same function with your new position. You mark the tile as visited. If you are ever in a position that you cannot make a move, you backtrack by calling the same function with your previous position…

That was kind of covered earlier in the thread (the OP was looking for grid-based movement with a specific logic, rather than just general straight-line movement).

That sounds more or less like Dijkstra (or something similar). Anyway, this type of pathfinding is basically a solved problem, so there’s no particular need to develop an algorithm from scratch. A* is really pretty optimal for this sort of thing, and is a good go-to solution as far as grid-based pathfinding is concerned (or any type of pathfinding really, since A* is just a graph search algorithm, but with a grid-based system the implementation can often be made a little more straightforward).

hmm, yes. That’s why the ‘if’. The order in which you move 8 squares forward and 4 right doesn’t require path finding.

well, where’s the fun in that

Anyway, I looked at what A* is and it is probably the best way to go, indeed.