Isometric Pathfinding Optimization

Discussion of tools and resources for game developers

Post » Tue Mar 03, 2015 4:19 pm

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
B
7
S
1
Posts: 15
Reputation: 482

Post » Tue Mar 03, 2015 4:38 pm

+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.
Follow my progress on Twitter
or in this thread Archer Devlog
B
27
S
10
G
12
Posts: 627
Reputation: 8,331

Post » Wed Mar 04, 2015 9:37 am

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.
B
9
S
2
G
1
Posts: 48
Reputation: 710

Post » Wed Mar 04, 2015 12:13 pm

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.
Follow my progress on Twitter
or in this thread Archer Devlog
B
27
S
10
G
12
Posts: 627
Reputation: 8,331

Post » Wed Mar 04, 2015 12:59 pm

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.

Image
Follow my progress on Twitter
or in this thread Archer Devlog
B
27
S
10
G
12
Posts: 627
Reputation: 8,331

Post » Thu Mar 05, 2015 9:22 am

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?
B
9
S
2
G
1
Posts: 48
Reputation: 710

Post » Thu Mar 05, 2015 10:29 am

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.

Image
Follow my progress on Twitter
or in this thread Archer Devlog
B
27
S
10
G
12
Posts: 627
Reputation: 8,331

Post » Fri Mar 06, 2015 12:36 am

@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.
B
101
S
24
G
199
Posts: 4,216
Reputation: 114,674

Post » Fri Mar 06, 2015 1:13 am

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

pathfindingtranslation.jpg


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.
You do not have the required permissions to view the files attached to this post.
B
9
S
2
G
1
Posts: 48
Reputation: 710

Post » Fri Mar 06, 2015 2:51 am

Here is a demo about finding path on a hex board.
- click any purple tile.
B
101
S
24
G
199
Posts: 4,216
Reputation: 114,674

Next

Return to Tools and Resources

Who is online

Users browsing this forum: No registered users and 0 guests