Pathfinder

[Volutar]

Generaly, they say it doesn't matter how path is built, unless it's not optimal in TUs cost.
But this is wrong.
There are situations, when you need unit to keep straight line. So obviously if there are alternatives, unit must keep most straightest path possible.

Let me illustrate.

[Volutar]

Some dude already have been working on this "problem".
https://www.irontowerstudio.com/forum/index.php/topic,1720.0.html

And actually, XCOM game series have exactly this, "straight" version of pathfinding, which is the only acceptable pathfinding for this kind of games.

[Volutar]

Okay.
I've been using dijkstra algorithm for marking all possible shortest paths.
Each grid cell may have number of "vectors" which shows direction to the next cell of shortest path, though at the end all of these alternatives eventually will get to "start" point.

First case is most difficult. There are 2 alternative ways, which are absolutely equal in TUs cost. Final point (at the bottom of 1st grid) have 4 (FOUR) alternative ways out, so making optimized paths would be quite difficult.

Second case also have two alternatives, which seems to be quite okay, but actually it's not that easy. Final point at the right of the grid. So there are 2 ways - above horizontal bar, or below it. Which of it will be most straight? I think below one, because initial walk vector will be closest to vector to the target point.

Optimizing those "equal areas" to straight line is not hard. You just need to look through all cells (from the closest) which have only ONE direction, until bresenham line (LOF) is possible.

[Volutar]

If you want to play with application i've made for testing these "equal paths":
https://volutar.eu5.org/pathfinder.zip

Actually finding most "straight" path is quite hard as I see, though it's clearly possible.

[Volutar]

Another thought. Pathfinder shouldn't even try to go into/through black unknown areas... Say, how can they know the path in the unknown? Clicking into the darkness and going though the maze with one click is a kind of a cheat...

[Volutar]

If we use bresenham to figure out furthest straight trajectory possible, then we'll get weak path with low tension. Which is bad.
On the picture below you may see green line going way too far, so next segment become silly.
Note: Path traversed backwards from the final point (which is at the right), so green line will be too long. And even if we try to travese it in forward direction - it won't help a bit.
So we need some kind of algorithm, finding better "corners" for bresenham.

[Volutar]

Sort of success, though there are bugs possible - should test alittle.

Test program also updated.

[Volutar]

Hello again.
Another update. Now it recognizes objects and walls.

[Volutar]

Application updated. Now you can set source point with RMB and destination with LMB.
URL is the same: https://volutar.eu5.org/pathfinder.zip

[Daiky]

Do you plan to add in xcom specific things? Like ufo walls (that are objects acting as walls) and the stairs functionality? Also, it seems like an interesting project, but since it's a standalone application, I don't see the immediate benefit to the openxcom project - unless at some point you release the code and it's portable to the openxcom engine somehow.

[Volutar]

Daiky, ufo walls? what's the difference between them and ordinary walls?

[Daiky]

ufo walls - actually the diagonal ufo walls - are objects, but they don't behave like objects where you have to walk around, depending on the direction you walk along them.

Ok, never mind this,  I have this totally wrong , you can actually walk diagonally passed every object, so ufo walls don't make a difference... arggh, well even I can make mistakes

[Volutar]

Yeah, these diagonal ufo walls made with kind of trick: they used wall_diagonal + wall_corner interleaved, so they cannot be passed to move inside or out, though these wall_corners are almost invisible and can be passed like right green arrow on second screenshot without problem.

[Volutar]

I've begun to implement ufo map (saved games) processing (with all MCD data) with my pathfinder.
And discovered that we might be done something wrong.

First thing - they're using "is_wall" flag of MCD of some of objects (diagonal walls). This flag mean unit cannot walk by this tile diagonally (i've marked these objects with yellow dots). This explains why we can walk through north-east wall of Avanger, and cannot walk through north-west - they just haven't set this "is_wall" flag for north-east wall.

Second thing - UFO_140. WE can see they're extensively using diagonal walls flags even if it unnecessary (western and northern outside walls also work as "diagonal"), and if you can stand besides south wall of UFO, you cannot stand near northern!!! You can check it. I don't see any reason to do that.

Third thing - you cannot walk along diagonal walls in UFO (at least of this UFO).

[Volutar]

I think there should be TWO kinds of "is_wall" flags of MCD. Or probably this field should be a BYTE, not a BOOL field, and have 3 states: 0=not a wall, 1=SWNE(/) wall, 2=NWSE(\) wall, so we could make diagonal walk along these walls possible. Plus we can change these "walls" which have an 3 (object) type, and setup at 3rd byte (where object should be). I really don't know why they made this illogical decisions. There is an easy way to to fix this up and make it better.