Author Topic: Pathfinder  (Read 36662 times)

Offline SupSuper

  • Lazy Developer
  • Administrator
  • Commander
  • *****
  • Posts: 2159
    • View Profile
Re: Pathfinder
« Reply #45 on: October 17, 2011, 06:02:45 pm »
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 :D


There isn't any in TFTD either.

Volutar

  • Guest
Re: Pathfinder
« Reply #46 on: October 17, 2011, 07:43:06 pm »
Opening doors for free (without passing) depreciate this door tile passing TUs cost...
There are some options:
1. Door passing cost should be 0
2. Door opening (without passing) should cost same TUs_cost as passing it.
3. If door was opened (for free), passing through empty doorway will cost same value as for straight passing, if done in the same move. But there are dealbreaker thing outthere - when you will open the door (for free), and then see alien there - you may decide to go back (through same door which is in another position). Second "switching" (closing) will also cost 0, but going through door's old location will cost you TUs.

I wonder how it done in original xcom?
If you're going through closed hinged door which have alien standing behind it,  the door is opening and your move is aborted. So actually you do not cross the line, but door tile is changed to alternative (opened). Will it decrease your TUs for this "unperformed" move through the doorway, or it will be TUs-free?
« Last Edit: October 18, 2011, 05:59:32 am by Volutar »

Volutar

  • Guest
Re: Pathfinder
« Reply #47 on: October 19, 2011, 06:45:36 am »
Anyone?
As far as I remember, door open TUs (with right click) cost 4TUs, which is equal to door passing TUs. Though there are doors with 8TUs passing cost. I don't know if rightclick-opening cost 8 or 4 for those, but I think logically it should be 8, like if you're passing it. Otherwise manual opening will save some TUs which would be a gameplay bug.
« Last Edit: October 19, 2011, 07:15:49 am by Volutar »

Offline kkmic

  • Commander
  • *****
  • Posts: 582
  • Undefined
    • View Profile
Re: Pathfinder
« Reply #48 on: October 19, 2011, 09:28:35 am »
I'd like to stick with the TFTD approach, of no TUs cost when manually opening the door.

I agree that in RL it's faster to open the door (open, not crash through it) while walking through it in one continuous action than stopping in front of it, opening it wide and only then passing through  8)

But then, XCom soldiers are in full battle gear and when encountering a door they open it instead of just kicking it wide open (the door is not damaged, it just opens) so I suppose It's a little bit faster to open then pass instead on opening and passing it in one move  :D (they might hit the door with the weapon or backpack, or worse: https://www.youtube.com/watch?v=NvAvuJxk3w0)

My two cents   ;)
« Last Edit: October 19, 2011, 11:15:10 am by kkmic »

Volutar

  • Guest
Re: Pathfinder
« Reply #49 on: October 19, 2011, 10:14:56 am »
You can click at tile before door, open it manually and go further. If so, we can disable TUs for going through doors at all... But this is a obvious, while comfortable BUG. I don't think we should replicate this bug... it's like... we'll keep bugs if we like them, and fix those which are uncomfortable... Firstly, it's a double standard (which is bad). Secondly, such approach (automatic - more TUs, manual - no TUs) is illogical, and have no excuse.

In order to keep gameplay coherent, we either make manual door opening costy (equal for passing through it), or make door open free, both for manual and for walking through.
« Last Edit: October 19, 2011, 10:20:02 am by Volutar »

Offline kkmic

  • Commander
  • *****
  • Posts: 582
  • Undefined
    • View Profile
Re: Pathfinder
« Reply #50 on: October 19, 2011, 11:20:05 am »
True, this might be a "convenient" bug. I always considered to be a little bit weird to be able to open the door at no cost, but pay a "open door TUs cost" when passing through, but since I always stop in front of a door to avoid some of the reaction fire, it was, as I said, convenient.

Well, then set the cost of door opening at 4 TUs, as for simplicity's sake we should consider opening the door has the same cost regardless of the intention: open only or pass through

Volutar

  • Guest
Re: Pathfinder
« Reply #51 on: October 19, 2011, 12:11:47 pm »
In TFTD right click door opening done with calling "walk" function to next tile with "no_move" flag set, so unit stays where it is (and keeping kneel state), just door open is happening. They just disabled TUs_Consume call, if it's a manual opening. If they reenable it - unit would stay, but TUs would be consumed as if it walks to this tile (which is wrong). I think they could be thinking of adding "half_walk" functionality(count only wall crossing TUs), but forgot to get it done (stayed at temporary "no cost"). Implementing such "door crossing" TUs consume would require alternative "walk_to_neighbor" or even "walk_to" functions. Well, they've made alot of weird stuff which hardly could be explained logically.
So such illogical things are not the best reference.
« Last Edit: October 19, 2011, 12:28:10 pm by Volutar »

Offline kkmic

  • Commander
  • *****
  • Posts: 582
  • Undefined
    • View Profile
Re: Pathfinder
« Reply #52 on: October 19, 2011, 01:54:33 pm »
"Half walk"? Meaning that opening the door without passing was supposed to cost 2 TUs?

How about sticking with the intended (but not implemented) functionality for opening without passing?

But then, how should "open and pass" be considered? "Half walk" (4+2 TUs)? Or "full walk" (4+4TUs)?

Volutar

  • Guest
Re: Pathfinder
« Reply #53 on: October 19, 2011, 02:44:11 pm »
For door passing there are 4..8TUs... For ground passing is 4TUs (almost all the time). When your unit makes a step inside, it opens the door and step to next ground tile. So its cost will be 4..8+4=8..12TUs.. By "half-walk" I meant wall passing (door opening) without getting to the next tile. So it obviously would be 4..8TUs (depending on door type).

By the way I asked a question and nobody answered: how many TUs will be consumed when you open a door without entering it in original XCOM1??? Your unit is standing next to the door, and alien is standing on the other side of it. You're left-clicking to tile behind the door. Door become opened, but your unit will stand still (because tile is occupied).

For example, getting inside UFO with one walk click will cost: 8(door)+4(ufo ground tile) = 12;
Manual (controlled) walk will be: 8(door manual opening)... looking inside, + 4 (ufo ground tile) =  same 12;
So there will be no difference between manual opening and going inside and going inside with automatic door opening.
Though the only case when manual door opening will have obvious benefits, is when your unit opens it while standing diagonally.
Actually I think this right click door open (apart from cheat of free TUs), was implemented with a thought of DIAGONAL door open... In all other cases it doesn't matter - manual or not.
« Last Edit: October 19, 2011, 02:47:52 pm by Volutar »

Offline Daiky

  • Battlescape Programmer
  • Administrator
  • Commander
  • *****
  • Posts: 904
    • View Profile
Re: Pathfinder
« Reply #54 on: October 29, 2011, 05:28:05 pm »
Next version of openxcom beta will have the option to first preview the path. It's just a basic coloring of the tiles on the path in green or red (if it's out of your TU range).
The first click will let you preview the path calculated by the pathfinder, a second click on the same tile confirms the path and makes the unit move.
It does not fix the problem you found with equally weight paths not choosing the best path, but allows for more control and information to the user what route the unit will take.
« Last Edit: October 29, 2011, 05:30:35 pm by Daiky »

Volutar

  • Guest
Re: Pathfinder
« Reply #55 on: October 29, 2011, 05:38:37 pm »
Nice. But I think coloring here is too "rough". Is it possible to make it more pale?

Offline MKSheppard

  • Colonel
  • ****
  • Posts: 249
    • View Profile
Re: Pathfinder
« Reply #56 on: October 30, 2011, 03:00:41 am »
This is very, very, awesome! It takes a lot of the guesswork out of moving your units and actually fits in with the rest of the user interface!  ;D

Offline Daiky

  • Battlescape Programmer
  • Administrator
  • Commander
  • *****
  • Posts: 904
    • View Profile
Re: Pathfinder
« Reply #57 on: October 30, 2011, 05:56:52 am »
Volutar, yeah, the colors can be tweaked (although remind there is only about 16 colors ;)
And I probably make an option for a JA2 style preview, where the preview automatically is shown when you hover the mouse x milliseconds over a tile, so you can still walk with 1 click instead of 2.

Concerning your improved pathfinder, while theoretically it's nice, when I go back to your original "problem", I think with a simple "patch" to the current openxcom A* pathfinder I can cover 90% of all situations where you will have an actual problem in the game.

The original problem was: when you have multiple solutions with the same TU cost, you want a straight line solution for the sake of keeping out of enemy line of sight or line of fire.
To me this implies that this is a situation where you ask for a simple path from A to B in a plain field with all equal cost tiles and where there are no obstacles to avoid. In such a case you want a bresenham calculated line (= as straight possible line on a grid).

Knowing this, I imagined a patch to the current A* pathfinder where I first of all do the normal pathfinding (to know the total TU cost of the optimal path). And after that I do a bresenham path check from start to end, and if this bresenham path check did not get blocked I check the total TUs of that bresenham path is equal to the TUs of the optimal path.
When this is true, I take the bresenham path as my optimal route.

If you watch a lot of xcom LP movies you'll see how people, when there is possible danger of aliens shooting at you, will generally move forward in smaller, very simple paths. They will actually take control over the path themselves, instead of asking the AI to do a complex path and trusting it will do a good job.
Because when there is a blocking object in your path, for example a tree in the middle of a straight path, you need a very advanced AI to know which way around this object is the best, if both ways around it are the same cost.

Also, this patch will take me less than an hour I think to program. While rewriting the pathfinding from scratch, will take me more time, including possibly new bugs. Precious time I better spend on implementing large units pathfinding and a lot of other issues that are asking attention (like the ufo walls you said) :)

Volutar

  • Guest
Re: Pathfinder
« Reply #58 on: October 30, 2011, 08:18:57 am »
Daiky, by your words, you are actually going to replicate what i've suggested, but in more complicated manner.
If I got you right - you're going to "post-process" your A* path. Take A as start point and B - point next to it, and if bresenham check succeed (and TUs cost the same), you'll "fix" your path. Then you'll get advance for B point, and try next bresenham, and so on until it fail. Then are you going to try next A as A+1? Or take it from B? Because in second case you'll get what I've called "not tensed path" (though it will work faster). And will walk by green-purple lines instead of blue.


So in order to keep path "straight" you have to get advanced your A point step by step, not by leaps of already scanned.
And you probably will get same results as mine. :)

P.S.: I've though of your method and found it will get not very nice "alterations" when there are small obstacles on the way. I believe you have to scan every B possible (not until bresenham failed) for every A. Because there are situations when you can get multiple bresenham failures, but after a while you can get bresenham success (when you get around some obstacle). I think I may try to do my own "alterator" for path.
P.P.S.: So you basically need "check_bresenham" function from A to B which will return TUs count for this "bresenham" path or -1 if there are obstacles, "replace_path_with_bresenham(A,B)", and simple double loop of A from 0 to path_size and B from A+1 to path_size (probably there could be some condition to break this loop early, for optimization sake). For maximum pissible xcom1 path with 25 steps, it will require 325 bresenham checks. For path with 50 steps it will require 1275 bresenham checks. For 100 steps - 5050 checks. One level maze of xcom map (50x50 tiles) will require 3126250 checks.

P.P.P.S.: Saying about smaller control. Okay, some people indeed prefer to move by 1 step in such situations. But not every one. Moreover, AI will suffer more, because it will get unwanted attention more often because of this.
« Last Edit: October 30, 2011, 09:56:24 am by Volutar »

Offline MKSheppard

  • Colonel
  • ****
  • Posts: 249
    • View Profile
Re: Pathfinder
« Reply #59 on: November 03, 2011, 05:03:15 pm »
The first click will let you preview the path calculated by the pathfinder, a second click on the same tile confirms the path and makes the unit move.

Suggestion.

How about having it so that holding down SHIFT makes the pathfinder appear after you have selected a unit?

This lets you preview the path without clicking; an important consideration if OpenX-COM is going to be played on laptops with badly laid-out mousepads.