Isometric Pathfinding Optimization

Greetings,

I have been working on an isometric game using Construct 2. I find that there is a level of inaccuracy that is inherent in the system when using with isometric games.

I would like to propose an option to be able to set the angle of the grid lines to better optimize with isometric games. Perhaps "Horizontal Lines" and "Vertical Lines" and be able to set them independently.

I am hoping Scirra can implement this into Construct 2, or if someone can direct me to the pathfinding code I will attempt to make an addon myself.

Any help is appreciated!

• Cory

+1 for that. I've noticed that too. I managed to do some tweaks to the parameters to get it somewhat better but still not good enough especially in tight areas. Had to rethink my level design a bit and make things a bit more spacious.

Can you not compute the pathfinding from an overhead perspective grid, and then convert it into isometric coordinates?

It's a bit hacky, but that's what I'd try first.

Edit: Let me know if you need help with isometric to square position translation math. Sometimes it's hard to visualize.

Based on what I have read in the manual on pathfinding, this kind of thing wouldn't be an easy fix for them (arbitrary shaped grids), and it would still leave issues with other tile types, like hex.

Aside from making an overhead view clone to do pathfinding on, all you can probably do is decrease cell size, which would hurt performance a lot.

I was messing around with the collision boxes and got some pretty nice results but would be great if you in some way could have one set of collision boxes used only by pathfinding.

I was also messing around with some events to make some kind of home brewed pathfinding. Basically what I did was ignoring all collision boxes placing dummy sprites in a chess board pattern (for diagonal feel sort of), and removing sprites in this checkered pattern where i didn't want pathfinding to go. Worked quite well, but a bit more work to do. Will try out some more tests on it later.

Here's an explanation on what I'm working on. I will also try to use an array approach to get the valid positions and callculate a path based on the array. Or at least i think I'm on to something... >_<

1's are valid positions to stand. 0's you can cross but not stand on. 2's you can't cross or stand on.

You mean you're writing your own pathfinding to use the array? It looks like it could work.

All of these tiles are quads in an even grid, why not redraw the map as squares (rotated) in a normal grid and do the pathfinding there with the out of the box solution, and then copy the results by translating the coordinates to the isometric display?

Can you set one sprite so its movement is dependent on another sprite's movement?

e.g. Sprite 1 moves down, and Sprite 2 moves at an isometric angle the same distance as sprite 1 moved down?

That could work too, but for my simple mind this chessboard pattern seamed easier for me to grasp than to translate straight coordinates to isometric ones. I'm not really a programmer or coder, so I'm just messing around with it, to see what's possible. But i guess what you're saying using offset you can translate any array position to a map shape like this <> ... Just like a tilted array.

For example so the translation would be something like this?

Line 1, cell 1 would have an offset of X,50 Y,0 (of 100) It would have the top position middle of the screen.

Line 1, cell 2, would have a position of X,60, Y,10, would be one the second row, slightly offset to the right from the center.

Line 2, cell 1 would have a position of X,40, Y,10 would be one the second row, slightly offset to the left from the center.

"Y" would increase for every line, and X would decrease by 10 for every position on the Y axis, and increase by 10 for each position on the X axis.

Then the array would translate to something like a shape like this -----> <>'

Anyway i still prefer the chessboard pattern because it's easier to grasp and to visually comprehend and woudn't restrict your map to a shape like <> ... You map could still be isometric, but have any shape within the [ ] boundries of the array.

In the chessboard layout you could replace any number with a 2, to block movement. Just translating the the array to isometric positions you can't control where you want to block certain movements. Or you have to add it in code.. restrtricting movements in certain directions based on the number and position of stuff relative to your position, and it just becomes an headache... at least for me.

Here's an example of the control you have in the chessboard pattern, that would be much harder to control using your suggested translation. Top example is using a small object like a fence on the same position. The lower example a big thing like a building.

MVG

tunepunk

If you are moving on a chess board, try this plugin which could find a path on an orthogonal or isometric, or hexagonal board. it is a part of my board plugins systems.

tunepunk

Yes, something like that. However, as in your example, you wouldn't necessarily be limited to full tile collision only, if you rendered it out as an alternate map and did away with the array based pathing.

You can use arbitrary collision bodies.

[attachment=0:34o2jhrb][/attachment:34o2jhrb]

Make sense?

It's basically like this:

All the AI is really playing the game on map A, but their movements are copied by the sprites on map B (after applying the isometric translation to the coordinates).

You can hide map A if you want, off screen, or just don't render it if that's easy. Or even use it as a mini-map in the corner.

So you can use arbitrary collision shapes, and as small or large a cell size for pathing as you want.

However, if you want to force your sprites to stop in the center of tiles for tile-based movement (maybe you're making chess, or a rogue-like), and you only have those limited collision cases, then your way is actually pretty good.

rexrainbow

Thanks! I'll check that out.

Here is a demo about finding path on a hex board.

• click any purple tile.

rexrainbow

Seems to work well, although I can't tell much without obstacles in the way to trip it up.

However, I am seeing some aesthetically odd results.

For example:

[attachment=0:3scttim7][/attachment:3scttim7]

Nine steps, yes, it's technically an acceptable path, and one of the shortest paths, but visually it's not the shortest path (just one of the shortest options given the tiles).

Maybe you can add in a distance check, such that it will choose the shortest path that also *looks like* the shortest path, in that it's also the shortest linear distance?

Just an idea.

Here is a demo about finding path on a hex board.

- click any purple tile.

Nice example. Takes me back and makes me wanna do a UFO: Enemy Unknown type game.

Better, how can i sync topdown pathfinding with isometric projection. Problems: Sprite rotation in topdown (get variables to sync with iso frames) and can't reduce rotate speed (one second).

JamesXXXYZ

Sorry, I don't understand your problem. Can you rephrase, or explain more?

If your topview sprite is pointed North, that would mean your Iso sprite is pointed at the angle that corresponds to North in the top view grid (such as up and right, or up and left, depending on how you translate it).

Rotate speed?

MVG

[attachment=0:3nb20462][/attachment:3nb20462]

When topdownsprite direction is right then isometric frame is 0.

Problem is when i wanna use topdownpathfinding then i don't get a variable, so i can't sync with my isometric frames (40 frames for 360°).

Pathfinding rotation speed update every second, but i need every 0.05 seconds.