Hi all I have a stupid question but i cant figure it out:) Maybe i am just tired and tomorrow i will get it done but anyways i thought i would ask since i think a lot of you guys have to have done this before. Here is my Problem: I was going to program the A* Pathfindingalgorythm for a iso map to see how it works. But i got stuck calculating the distance between a Tile1(x/y) and a Tile2(x/y) as the article i read was for square tiles and not for iso ones. The article wants me to do this: // H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement. We then multiply the total by 10. // But how do i do this in a isometic coordinate system. sorry for my bad english but i am tired and german:) thx in advance a link to a site where i could read up on this would be more than enough for me:) night all:) Rozik

Well i found a way to do it but i am not sure if it is a good way to do it cpu wise

here is the code if anyone cares:

Quote:Original post by Rozik
Hi all

I have a stupid question but i cant figure it out:) Maybe i am just tired and tomorrow i will get it done but anyways i thought i would ask since i think a lot of you guys have to have done this before.

Here is my Problem:

I was going to program the A* Pathfindingalgorythm for a iso map to see how it works. But i got stuck calculating the distance between a Tile1(x/y) and a Tile2(x/y) as the article i read was for square tiles and not for iso ones.

It's useful to think of an iso map as a square map when working with game mechanics behind the scenes. Isometric perspective is simply a way of visualising the map to the screen, think of it as a set of rotations. You have to deal with these transforms when drawing objects or dealing with user input from a mouse, but when you are doing something purely in game world space (like pathing) it's better to think in terms of square tiles, the connectivity will be exactly the same.

Quote:
The article wants me to do this:
//
H can be estimated in a variety of ways. The method we use here is called the Manhattan method, where you calculate the total number of squares moved horizontally and vertically to reach the target square from the current square, ignoring diagonal movement. We then multiply the total by 10.
//

For now consider a square map, I'll expand this to iso later. The Manhatten distance only works as a heuristic if your map is 4-connected (you can only move north, south, east, west). If your map is 8-connected (you can move diagonally through the corners of tiles) then the Manhatten is not an admissable heuristic.

For A* an admissable heuristic is one that never overestimates the distance from a node to the goal. If you are allowed to move diagonaly and the Manhatten heuristic assumes that you can not then it can overestimate. For 8-connected maps the heuristic is just the larger of the vertical or horizontal distance, (Diagonal move give you a move in both direction as a single step, so you can cover the shorter distance while moving the larger.)

nx, ny = node position
gx, gy = goal position
dx = abs(gx - nx)
dy = abs(gy - ny)
H(nx, ny) = max(dx, dy)

For your map you can choose if it is 4 or 8 connected. To apply this to iso this depends on if you allow objects to move up, down, left, and right as well as towards the corners of the screens. Do you allow moves through tile corners as well as tile edges? If so then you have an 8-connected map. Remember to do the distance calculations in map space not screen space.

Quote:Original post by Wyrframe

Quote:...but when you are doing something purely in game world space (like pathing) it's better to think in terms of square tiles, the connectivity will be exactly the same.

Not quite. That would be true if Rozik were using a diamond layout; from that code segment, he appears to be using staggered rows, not transformed diamond. Unless that's just some very odd code for generating Manhattan paths.

That's a good point, using a staggered map format will make getting world space coords more difficult. However node connectivity in the map should still be the same in both representations.

Instead of the standard 4 and 8 connected models we can think of nodes as connected in two ways:

Edge connected nodes share a long edge. In a standard rectangular map these would be north, south, east, and west of the node. In a staggered map they will be found at at adjacent y rows, but not in the same y row.

Corner connected nodes share only a corner. In a standard map these will be along diagonals from the node. In a staggered map they will be found in the same y row and 2 rows away above and below.

A 4-connected map allows only movement through edge connected nodes, an 8-connected map allows movement through both edge and corner connected nodes. Regardless of map representation the set of nodes an agent can move to from a given node is the same.

At this point we have two choices. We can convert nodes from staggered map space into a space where movement between edge connected nodes is parallel to a single coordinate axis. (I'll refer to this space as world space, it's the same as the standard 2d space used by a game with square tiles). Conversion into this space isn't actually that bad. Staggered map space is very close to screen space, except that x-coords are offset by 0.5 on every other row. Once you account for this stagger effect then it's very close to a screen to world space transform.

The other option is to do the distance calculation in staggered map space. Consider the following staggered map: (sorry these aren't diamond shaped, you'll have to use some immagination here)

[0,0] [1,0] [2,0] [3,0] [4,0]   [0,1] [1,1] [2,1] [3,1][0,2] [1,2] [2,2] [3,2] [4,2]   [0,3] [1,3] [2,3] [3,3][0,4] [1,4] [2,4] [3,4] [4,4]   [0,5] [1,5] [2,5] [3,5][0,6] [1,6] [2,6] [3,6] [4,6]

Consider node [1,2].
It has 4 edge connected nodes: [0,1] [1,1] [0,3] [1,3]
It has 4 corner connected nodes: [0,2] [2,2] [1,0] [1,4]

Lets consider a slight modification to the staggered map: We'll double all x coords and add one to x coords on odd rows, that gives us:

[0,0]     [2,0]     [4,0]     [6,0]     [8,0]     [1,1]     [3,1]     [5,1]     [7,1][0,2]     [2,2]     [4,2]     [6,2]     [8,2]     [1,3]     [3,3]     [5,3]     [7,3][0,4]     [2,4]     [4,4]     [6,4]     [8,4]     [1,5]     [3,5]     [5,5]     [7,5][0,6]     [2,6]     [4,6]     [6,6]     [8,6]

This leads to a few obeservations: Corner connected should always be prefered over edge connected ones. Any even change in y (dy) can be covered in dy/2 steps. And, in the modified space, even changes in x (dx) also require dx/2 steps. These distances should always be positive so we'll assume they are the absolute value of the change in the coordinate. Now if we could only make corner connected moves we could reach any other reachable node (we can only reach half of them this way, think of a bishop in chess) in dx/2 + dy/2 steps.

Each remaining node is one step away from a node we can reach using only corner connected moves. Any path using only edge connected moves longer than length one will cross a corner connected path that is the same length or shorter. (take a node in the graph and consider all length 2 edge connected paths from it) So if we find the length of shortest corner connected path to a node adjacent to our goal and add one to that length we have the shortest possible path length to the goal. For the set of corner reachable nodes this length is just (dx/2 + dy/2) - 1. And the length to the actual node is dx/2 + dy/2.

For the remaining nodes, the nearest corner reachable node will be (dx - 1)/2 + (dy - 1 / 2). Since these changes are always odd we could use floor(dx/2) + floor(dy/2) instead. The length to the actual node is floor(dx/2) + floor(dy/2) + 1.

These formulas are very similar, in fact they are only off by 1.

Even: dx/2 + dy/2 = floor(dx/2) + floor(dy/2)
Odd: floor(dx/2) + floor(dy/2) + 1

Remember that dx and dy are always both odd or both even (see above graph) so we can combine these formulas into:

ciel(dx/2) + floor(dy/2)

Of course these are still in terms of the modified map space:

dy = abs(y1 - y2)dx = abs(f(x1) - f(x2))f(x) = x * 2 + 1 : odd       x * 2     : evenx1   | x2   | dx                        |dx / 2------------------------------------------------Even | Even | abs( 2 * x1 - 2 * x2 )    | abs(x1 - x2)Even | Odd  | abs( 2 * x2 - 2 * x2 - 1) | abs(x1 - (x2 + 0.5))Odd  | Even | abs( 2 * x2 - 2 * x2 + 1) | abs((x1 + 0.5) - x2)Odd  | Odd  | abs( 2 * x1 - 2 * x2 )    | abs(x1 - x2)Using some fun with truncation and division we could get that all in one formula, it would be pretty nasty though:dx/2 = abs((x1 + (x1/2 - floor(x1/2))) - (x2 + (x2/2 - floor(x2/2)))) 

Remember this is all assuming an 8-connected map, it's very different for a 4-connected one. All that nasty/even odd stuff is a result of using a staggered map, I don't really see a way to get around it though, you would need to handle those cases in the conversion to world space too.

Quote:
Either way; you can just perform a simple world-space query (distance between two points, pythagorus, (x1-x2)^2 + (y1-y2)^2 gives you distance squared) only if you have merely transformed the world by rotation, scaling, etc.

If you do something nasty and complex, like a staggered layout, when going from data to world, then the solution will be similarly nasty and complex.

Yep, as shown above staggered maps make the math kinda ugly. One quick point about the distance formula though, it may not be the best choice for tile based A*. For 4-connected maps it is an admissable heuristic, but it could run slower than manhattan. This is because it always underestimates unless the path is parallel to a coordinate axis. (It assumes you can cut the corner when you can't.)

For 8-connected it's not even admissable, it will overestimate the distance. This is because diagonal moves are twice as fast as two axis-parallel moves in 8-connected space. This may actually work out well, there was an interesting article on A* with inadmissable heuristics in Game Developer a couple months ago, but you are no longer guarenteed to find the shortest path.