Pathfinder

[DaiShiva]

From a map debugging standpoint, I think it would be useful if it showed the path and the total TU cost between two points. So that when your guy makes a move you dont think is reasonable, you can see why it goes around certain tiles instead of passing through them.

Thers a couple ways I can think of to interface with your executable to generate paths between two points of a map - a C-interface or parsing stdout from your exe.

[Volutar]

Hey, are you crazy? "parsing stdout" After finishing pathfinder algorithm I will gladly give you my code... Anyways, don't bother about that.
I think you're right at least about one thing - pathfinding definately will be helpful in mapeditor for better ROUTE visualization (trajectories between different route nodes).

[DaiShiva]

Yeah that was my thinking as well - adding it to the route viewer

[Volutar]

Another proggy update.
Now it work in 3d (I hope).

On attached image there's BARN. Starting point is marked blue on level2, destination point is purple on level2.
Unit goes up, then over the roof, down to barn entrance, then to the stairs, and towards destination point.
It don't know anything about lifts yet, and Stairs don't work as they should (they don't make any inter-level switch), and max elevation is not implemented. But I think it's not that hard to do.

==Addition:==
Application is uploaded. You can use any of your xcom1 maps (from battlescape savegames, just replace contents of /game with appropriate /GAME_XX).

[Volutar]

Here is updated version. Now it can:
- Use lifts
- Go stairs
- Fall (if can't fly - fly mode is triggerable)
- Falling into objects (diagonal walls) replicated bug
- Going upstairs into objects - replicated bug (in Avanger - going from ramp up into diagonal wall)
Still can't:
- Go downstairs level down without falling (this could also be in original)
- Getting upstairs to next level if pointing on the same level "behind" the steps - it just goes around to pointed location whilst in original it goes up level
- Nicely smooth path if it's broken into different Z levels (though it should go by bresenham when going up to the hills).
Known bug:
- Path trace slightly broken when source point is in the air, while unit can't fly, and pointed somewhere on the ground level (not all falled levels traced)

[panther]

Wow! This is really impressive.
The "known bug" shouldn't really matter, does it? Since falling things should fall down all the way first...

[Volutar]

Nah.. I've fixed it (app updated). It just required for extra value for equal distances (when unit falls TUs aren't consumed).

[Volutar]

Interesting thing... Going straight by ramp is more costy than immediate jumping off.
Folowing path takes 30 TUs, while straight path (which is chosen by UFO pathfinder) will take 32 TUs.

Strangely, in original UFO, it can be either 30 or 32 TUs when going down ramp. It can be either 4 or 6TUs when going through Avenger door on ramp. It consumes 6TUs when stopping right on upper ramp segment, and 4TUs when going through it without stop. This is really strange and subject to figure out the reason.

===Added===
Found another thing. When you're pointing at ground level for going outside - the cost is 30TUs. When pointing on same tile but level2 - the cost is 26TUs... how's that?

I've modified TUs cost for  ramp tiles from 2 to 6...and going by pointing to ground level become 42TUs, while when pointing to up level stayed 26TUs... Trajectory is absolutely the same.

[Volutar]

Another test in UFO: Enemy Unknown. Ramp extra TUs was given 0. I.e. ramp walk cost is 4TUs. And modified ground TUs from 4 to 8!.. So going to ramp and 4 tiles beyond should cost... 4+4+4 + 8+8+8+8 = 48 but actually it was 50TUs (extra 2 TUs may be because of "door"). But when I pointed 2nd level from the ground, it was 30TUs only! It was like 4+4+4+ 4+4+4+4 = 28 (+2TUs for "door").
So obviously, if unit will be going lower level than pointed, he will go with TUs cost like he would be flying... He gets TUs cost of tiles of level of the target, but actually will walk on the ground.

This is real bug, which can save alot of TUs if used properly. I don't know if anyone have discovered this earlier... Anyways this could be used and people might be expecting same pathing behaviour (even it's not fair).

Did you know you can walk on water? In polar terrain.. If you point directly from craft (2nd level) over water tiles (also 2nd level).

https://www.ufopaedia.org/index.php?title=Exploiting_Collision_Detection
I guess this is of the same thing... They are calculating route through the level you're on, and TUs of your level, even if it changed during walk.

[Volutar]

This is field rendering. 60TUs are marked with light green and 60TUs with light pink (80 overall + 20 reserved).
As you can see - it's not a round field, but rather "octogonic". Blue cells have TUs=0 to passthrough, red circles are objects which cant be walk thorough, but can be walked by diagonally. Light purple cells are hills (or ladders, and more intense color - more elevation it has).

[Volutar]

Application updated. Some bugs was fixed, and added functionality of "GAME*" folders scanning, to switch map from different saved games (by combobox). Also several examples have been put.
I foresee another bug. When you getting through hinged door, it switched to other position, and there could be situation when your unit goes through one door two times. This issue haven't been taken into acount yet.

[Volutar]

I wonder how currently A* pathfinder handle hinged door double open?
Daiky, do you handle this?

[Daiky]

Volutor, I think I know what you mean with hinged door double open, but I'm not sure.

Is it where you first have to close the hinged door because it's in your way, and then open the door again to walk inside the room/building? If it's that case, the pathfinder will only take into account 1 time the door crossing TUs. Because the pathfinder itself will not change the state of the door, the state of the door only changes when you are actually walking through it.
Is it a big problem? I don't think so, as most people will see this as expected behaviour. In real life you are not going to fully close the door to open it again. So I think the bug is "fair".

[Volutar]

Yeah, you got me right. And still, this is a bug, and pathfinder which meant to be picking most optimal route, will pick route with double-opened doors... i.e. not optimal.
I think it should consider concequences of going through the door... otherwise it will choose not the best path.

Indeed pathfinder doesn't change state of the door, I've faced same situation. But it doesn't have to. I believe there is a way of considering this.

[Daiky]

Unless you would change the TU cost of walking through a door so it is the same as walking around the door.

Hmm, this reminds me... I don't think in openxcom there is any TU cost of opening a door with rightclick