Stairway bug solution found ?

[Duke]

After spending many evenings analyzing, debugging and suspecting innocent functions, I finally could make stairways work again. As often, the solution is very simple.
In fact, it is so obvious that I could also imagine that it has already been considered but declined for some reason. That's why I'm asking here instead of posting a patch.

I tested with the fighter_crash map, the stairway in the 2-story building next to the dropship. It has 8 stairs and is 3 cells long. IIRC from playing 2.2.1 pretty much all the stairways in UFO-maps look like that.

Question 1: is it true that most stairways look like that ?

The routing/pathfinding code uses two constants

Code: [Select]

#define PATHFINDING_MIN_STEPUP 5
/* Minimum height for an opening to be an opening in step units (model units/QUANT)
 * Must be larger than PATHFINDING_MIN_STEPUP!!
 */
/* common/routing.c */
#define PATHFINDING_MIN_OPENING 6
They are given in QUANT units, which is 4. Thus the maximum amount of model units an actor can climb per move evaluates to 20. The delta between two floors is 64. So getting up to the 2nd floor with 3 moves of 20 each is impossible.

So I increased those two constants by one and it works nicely
If you want to test it, remember to recompile ufo2map as well and rebuild the map(s) you want to test with !

However, this solution may have sideeffects. Things may become climbable that are not supposed to be. Like
- small crates on the floor
- low railings of a bridge
- mild slopes

Question 2: Can any of the experienced modelers think of places in the maps where a height of >= 21 was used to inhibit climbability ?

[Mattn]

we had a discussion about that on our mailinglist - please see http://lists.killfile.pl/pipermail/ufoai/2008-November/000908.html for more information.

[Duke]

Ouch. Yet another place for bug infos :-/
Anyway, Thx for looking it up for me.

Unfortunately, that discussion didn't lead to a *decision*.
I'd suggest we start with incrementing the values by one. That should solve >90% of the stairway problems.
We can then focus on the remaining (and/or evolving) probs.

[Mattn]

that is something i'm not able to decide - wilminator is still working on that code. also i'm not sure how many bugs this will open in terms of walkable chairs and tables....

that's really something wilminator should comment on.

[Destructavator]

Actually, being able to climb on top of chairs and tables can make sense from one perspective - I can imagine, in the heat of battle, a soldier running around, dodging bullets/plasma blasts/whatever, and leaping over a chair or on top of a table in combat.  Come to think of it, it would also be nice if they could dive under a table before jumping back out on the offense, but I'd imagine that would be too much work, at least at this point, for the coders and animators.

Just my $0.02.

On the other hand, when weighing bugs and playability against each other, would you rather still have unusable stairs and therefore very difficult/impossible maps, or a bug where soldiers sometimes walk on top of objects?  Which bug is worse?

[bayo]

and climbing one level

And a little out of this topic: Is a model format with real time skeletal animation will help to expend the current animations (climbing, use ladder, throw a weapon to a friend...), or it will change nothing?

[Duke]

First off, I apreciate Mattn's decision to leave it up to wilminator. After all, that part of the code is his 'baby'. Imho that's a good policy

I certainly don't want to step on wilminator's toes, but as he seems to be RL busy atm, we might be able to help him by collecting some further insights on the routing/pathfinding bugs in order to speed up the process a bit.

Mattn and wilminator (and I) are simply not sure what kind of problems the suggested increase of stepup height will create. The easiest way to find out is to give it a try
As lined out above, it's an easy change (and easily reverted). So if there are some volunteers who can compile their own exe AND do a lot of play-testing, it would certainly help.

@destrutavator:
Being able to step on top of chairs may be realistic in some way. But there seems to be another bug (in the tracker) which may not let him step down again (get stuck in the ceiling). Not sure though.

[Mattn]

i really think that the tracing and pathfinding code (in src/common) must be fixed first. once that is done we can talk about "minor" tweaks like those you proposed here.

and as always - help is welcome. though i will sync any future patch with wilminator. i'm just not enough inside this codepart yet.

[Destructavator]

@bayo: Regarding your question, I don't know the answer, but I can tell you that I've started work myself on importing the soldier models in blender and attaching bones for making more animations and cinematics, although I haven't gotten very far.  I'd imagine that having a new "source" file for Blender or another program with bones attached would be useful for adding animations, although I'm not sure if the bones would export back out to the MD2 format.  Even if they don't, it would still be useful for building new animations, and I've heard that there will be a need for this eventually, with plans to add the ability for soldiers to climb up and down ladders, etc.
If new animations are needed soon and you want to work together on that part, let me know and I'll share what I have so far.

[Duke]

i really think that the tracing and pathfinding code (in src/common) must be fixed first.

Uhmm...I didn't know there is also a known problem with the *tracing* code. Could you please point me to it ?? (if tracing doesn't work correctly, neither routing nor pathfinding will ever).

On a sidenote: the 'pathfinding' code itself is a run-of-the-mill A* implementation and seems to work nicely. Actually it isn't really used to 'find a path', but instead merely calculates the needed TUs for ALL possible moves of a given actor. It could be improved a bit, but as it runs amazingly fast for an A*...not now.

From what I have seen so far, the problem is in the 'routing' code. That's the part that pre-calculates every possible move on the map for an actor of a given size, starting in ufo2map and possibly continuing in ufo.exe. It seems to calculate the floor and ceiling of a given 'cell' (ie. x/y/level) fine, but sometimes fails to calculate the 'connection' between two adjacent cells correctly. I can prove it by displaying the routing data, but I haven't found the bug in the code yet.

I'm sorry if the above sounded like a 'teaching attitude' on my side, and I hope you don't take it as that. I was merely trying to synchronize the *wording* for what we are talking about.

[wilminator]

@Duke, you're right on the money with your description of how the pathfinding and routing code works.  Teach away 

You're also right about not getting the routing right if the tracing does not work.  And I think that there is an issue with the tracing.  Somehow, the traces between cells is not correctly detecting the presence (or lack there of) of brushes.  That is what I need to focus my efforts into.  I am also hesitant about the code that merges the random maps; I have not been able to assure myself that works 100%.

Getting back on the original topic, we could bump up the STEPUP values, but then we could end up with actors climbing over stuff they shouldn't.  It would get things working, but I proposed an additional trace that would look for finer step intervals, allowing for steep stairs or slopes that an actor could get up without allowing the actor to scale a cliff.  But that would also add more code and debug time, and we are already hurting from new tracing code.

I think that for the time being, at least to ensure that the tracing code is working, we should bump the STEPUP values to get stairs working as it would allow me to fix the other tracing issue.  Later we can decide to add more floor tracing or to leave it as is.

There may be another logic error in the routing code I am not aware of, but it seems that all fingers point to the tracing causing routing errors.  Compile your map with -tracefile and two csv files will be created in the directory of the map files.  The *.elevation.csv file contains the floor and ceiling of each cell in QUANT units, relative to the base of the current cell.  The *.walls.csv contains the passage size leading into the given direction.  If you open the *.walls.csv file in Open Office, the center number is the floor height for that cell and each number surrounding it is the passage size for that direction from the cell, with the top 3 numbers being north/+Y and the right 3 numbers being east/+X.  Negative floor values indicate the floor is below the base of the current cell.  What I am looking for is logical places where a wall should be detected but a passage is available, or vice versa.  Exact map and XYZ coordinates are helpful if known. 

If the issue is in fact routing, it will violate the values recorded in the trace files.  So far, I have not seen any more since the last commit I made referring to bad logic, about two months ago.

And thanks for the help! I feel like I'm drowning as of late...

wilminator

[Mattn]

you can also see that something tracing related is wrong when you try to compile a map with latest bunker version - see http://lists.killfile.pl/pipermail/ufoai/2008-December/000974.html

either the light traces are wrong, or the loading of the lightmap samples (but i suspect the first to be broken) - and maybe those issues are related.

btw. Mike, what about the patch i send to you about the curTile stuff in tracing.c?

[bayo]

@destrutavator, i am very interesting by using skeletal models (Half-Life .mdl, .md5...) for self project, but i dont have any skill or time to code that for UFO:AI :-)

[DuKe2112]

You are always talking about ingame maps, but those are usually way too complex to check them well.
Have you considered making a tracing/routing debugging map solely for testing?
Something with ever incresing stepups, all possibilities in a structured matrix.
I don't know how much work that would be, but it would ensure that you discover all bugs with it.

[Mattn]

@destrutavator, i am very interesting by using skeletal models (Half-Life .mdl, .md5...) for self project, but i dont have any skill or time to code that for UFO:AI :-)

we have very basic dpm (darkplaces model) - or with minor modifications skm (qfusion model) support. but the code could need some more love