36 replies to this topic

[Sonarpulse]

Well, if you have stretched tiles such as you say, then you can do 2D non-euclidean pathfinding, but I think we should keep relativity out of RTSs

Edited by Sonarpulse, 26 June 2012 - 09:30 PM.

[zoot]

How about 2D euclidean pathfinding?

[historic_bruno]

zoot, on 26 June 2012 - 05:19 AM, said:

Really? I imagined the pathfinder could just operate on the vector field as if it was 2D. So if a tile has been 'stretched' over a ledge, it will visually look like an overhang, but to the pathfinder it would still 'look' like it did before the tile was stretched.

Well if it's just one tile stretched instead of several, I guess that would work, it would mean separate logic for handling position under the hood compared to what's visible in world. I was thinking you might have several tiles overlapping instead of stretched. We could also make cliffs a purely visual effect and not allow pathfinding, territories, or building on the stretched part -- less than ideal.

[zoot]

historic_bruno, on 26 June 2012 - 11:59 PM, said:

Well if it's just one tile stretched instead of several, I guess that would work, it would mean separate logic for handling position under the hood compared to what's visible in world.

It already is seperate, as far as I can tell. The pathfinder works on a 2D logic, the renderer works on a 3D one.

Quote

I was thinking you might have several tiles overlapping instead of stretched.

Can you give an example of a case where that might a problem? One case I can think of is if you had a ravine type of thing and then stretched ledges on either side towards each other so they would form a 'bridge'. But the map designer would almost have to be on a special mission to break the pathfinder to do something like that in the first place

Edited by zoot, 27 June 2012 - 01:41 AM.

[Sonarpulse]

Well for part two it would be fun to have full 3D gameplay. Even if some things (bridges, walking on walls, sapping/tunneling, etc.) can be faked without it, 3D gameplay will lead to a much more robust solution.

@zoot even the slightest overhang technically causes those problems. In minor instances, the over extended cliff or covered area below can be ignored like historic_bruno said though.

Another solution for increased detail maybe is to sorta mip-map a heightmap based on the slope of a lower resolution. So for example with really flat surfaces the game sample like 4 points for every 4 tiles (making 1 terrain tile for every 4 game types), and on cliffs it samples 9 points for every 1 tile (making 4 terrain tiles for every 1 game tile). Hopefully that makes some sense.

[zoot]

Sonarpulse, on 27 June 2012 - 01:43 AM, said:

@zoot even the slightest overhang technically causes those problems.

What problems? What is the exact issue that arise? If there is a non-minor overhang, what is going to stop the pathfinder from ignoring the fact that it is an overhang and just treat it like any other ground surface?

Edited by zoot, 27 June 2012 - 02:02 AM.

[Sonarpulse]

The issue ASIAK is that the game expects one location per given X and Y, but with an overhang you have two. That said:

• Fake it method 1: You can chop things and pretend either the overhang or the area below it doesn't exist for game-play.
  
• Fake it method 2: With any surface "topological equivalent" (you know the whole donught = mug thing), you can fake it be distorting your coordinates (that's what I meant when i was joking about non-Euclidean.) However then either your pathfinder act dummer, or you need to teach it about stretching which will slow things down.
  
• When you can't fake it: things like bridges act are like portals in Portal if you try to stay 2D. Clearly path-finding would really need to be changed to get that to work automatically. (might be neat for pyrogenisis though beyond 0ad seeing the use of teleporters in other RTSs.)

[zoot]

Sonarpulse, on 27 June 2012 - 02:39 AM, said:

Fake it method 2: With any surface "topological equivalent" (you know the whole donught = mug thing), you can fake it be distorting your coordinates (that's what I meant when i was joking about non-Euclidean.) However then either your pathfinder act dummer, or you need to teach it about stretching which will slow things down.

First of all, I take issue with calling it "fake" as that implies that some "truer" method exist, which I don't agree with. That said, in which respect would the pathfinder be dumber? What would a pathfinder using this method not be able to do that the pathfinder currently can do?

[historic_bruno]

zoot, on 27 June 2012 - 12:11 AM, said:

It already is seperate, as far as I can tell. The pathfinder works on a 2D logic, the renderer works on a 3D one.

As I said above, not only the pathfinder, but most other game logic is 2D as well. We've never planned to have true 3D terrain or movement.

Quote

Can you give an example of a case where that might a problem?

I thought I already did, but here are some graphical depictions brought to you by MS Paint

Here's how terrain works currently, with 2D height map:


The brown rectangles are structures, though you can substitute other game concepts. The way obstructions (and thus pathfinding) work, the difference in height between the two buildings is ignored since it's a 2D obstruction map. Most of the time this works well, the only time it doesn't is when you have a building extending off a steep hill, it might block buildings underneath. But we don't allow buildings to be built on a steep hill so it doesn't cause much issue in practice.

Here's what you're proposing:



As you can see there are two buildings whose foundations only differ in height. If we still have a 2D obstruction map, then it's impossible to build both of these buildings because the one foundation's 2D obstruction would block the other And obstructions are just one example, as I said, all(?) other game logic is 2D including territories, pathfinding, vision/LOS, and range queries, so it's obvious to me anyway that we would need to extend them all to be 3D or pseudo-3D with special cases for this vector field terrain.

How else might it cause a problem? Well imagine the brown rectangles are units. One is a healer and one is a wounded soldier. Let's say the cliff is some ridiculous exaggerated height, maybe 200 game units. Well because the range manager is using 2D data structures, the healer and wounded soldier are almost on top of each other, therefor the one is in close range of the other (2D). Obviously the healer shouldn't heal the wounded soldier because it's out of 3D range, but it doesn't know that

Territories are another example, say your territory extends under the cliff to where the lower brown rectangle is. I come along and want to build on top of the cliff directly above, but I can't because territory manager uses a 2D data structure and ignores the cliff's height

[zoot]

I honestly do not believe any of those examples would cause problems I am not saying you are wrong, just that those cases should be fixable with minor changes.

historic_bruno, on 27 June 2012 - 03:56 AM, said:

As you can see there are two buildings whose foundations only differ in height.

As I see it, this is not true. The foundations differ also in which tile they are placed on. One of the tiles just happens to be rendered above (i.e. at a different height than) the other. That won't cause a problem for the pathfinder because:

Quote

The way obstructions (and thus pathfinding) work, the difference in height between the two buildings is ignored since it's a 2D obstruction map.

Regarding ranges:

Quote

How else might it cause a problem? Well imagine the brown rectangles are units. One is a healer and one is a wounded soldier. Let's say the cliff is some ridiculous exaggerated height, maybe 200 game units. Well because the range manager is using 2D data structures, the healer and wounded soldier are almost on top of each other, therefor the one is in close range of the other (2D). Obviously the healer shouldn't heal the wounded soldier because it's out of 3D range, but it doesn't know that

How is this different from what we have now? Units can already be placed at great distances from each other vertically while being in range horizontally.

Likely you have a much better understanding of the code than I do. All I'm saying is: I don't see it. I'll leave you to decide if that's just because I'm an ignorant f*ck

Edited by zoot, 27 June 2012 - 12:04 PM.

[myconid]

I think zoot is right on a lot of points, and I'd say Sonarpulse's method #2 would work around the problem that historic_bruno describes (with caveats). I also think that Sonarpulse's method #2 would be more feasible to implement efficiently than he believes.

Imagine that you are replacing the terrain's heightmap with a "normalmap", where the vertical Y component of the normals is equivalent to the heightmap's height values. The simulation generally doesn't need to know about the additional XZ components, as this stretching happens during rendering. Taking historic_bruno's two pics as an example, the simulation can just see the top pic, and the bottom pic is only generated by displacing terrain vertices/model positions by the XZ amount of the normalmap when rendering. The model positions do not actually overlap in the simulation.

The stretching can cause some problems, though. It may affect unit speed, with units passing over stretched terrain going faster (we'd need to reduce that based on the magnitude of the XZ displacement vector). More importantly, it would affect mouse input, as we'd need to also displace the bounding boxes used for that. You would also find that rendered unit LOS stretches with the terrain, unit AI can see further when the terrain is stretched, projectiles are thrown farther where terrain is stretched...

Most of those are not unsolvable problems, and would be possible to fix by changing distance queries to take the stretching into account. Calculating the LOS for rendering would be a huge pain...

tl;dr What zoot is describing is probably possible, but would need a lot of intricate changes and a ton of testing.

Edited by myconid, 27 June 2012 - 06:31 AM.

[zoot]

myconid, on 27 June 2012 - 06:29 AM, said:

The stretching can cause some problems, though. It may affect unit speed, with units passing over stretched terrain going faster (we'd need to reduce that based on the magnitude of the XZ displacement vector). More importantly, it would affect mouse input, as we'd need to also displace the bounding boxes used for that. You would also find that rendered unit LOS stretches with the terrain, unit AI can see further when the terrain is stretched, projectiles are thrown farther where terrain is stretched...

Good points

[historic_bruno]

I never claimed they were impossible problems, I said: "it gets ugly in a hurry if we want full 3D terrain. IMO this raises more problems than benefits."

And I'll stand by that statement until someone cares to demonstrate that it's as simple as zoot says (not the rendering alone but the integration with gameplay)

Though I should also mention that I'm not passionate about cliffs at all, we come close enough with the current simple height map for my liking. The texturing is ugly but myconid has shown that can be improved -- with no effects on gameplay at all, which makes me happy

[zoot]

I didn't say it would be simple. Just that there wouldn't have to be any relativity theory involved

[Sonarpulse]

Well, the "scaling" issue with number 2 is presumably we want game speed to depend on real world distance, not game tile distance. So we'd need to get the inverse of the terrain stretching and use it as a coefficient for unit tiles/second seeds. Then we would need to feed this same information to the pathfinder, or else it could only figure out the fastest path based on the number of tiles, not real-world distance.

[zoot]

I buy that. Still, I hope it wouldn't be inconceivably hard to do such a 'coefficient lookup' in the right places.

[Sonarpulse]

In your defense, after I wrote it, I realized that computing the stretch values from a 3D displacement map (r=x g=y b=z) would indeed be simpler than I thought.