[http://sourceforge.net/p/ufoai/patches/409 Item 409] imported from sourceforge.net tracker on 2013-01-28 20:39:33

The idea here is to skip microtracing if it doesn't help us, ie. if we already have enough headroom && can safely assume that MIN_STEPUP is sufficcient for the intended move.

Also did some refactoring because major parts in RT_TracePassage() were identical.

This patch brings CONNCHECK for fighter_crash down to 41 from 54s :)

Hoping for your approval...

===== Comments Ported from Sourceforge =====

====== aduke1 (2009-03-19 22:59:59) ======

avoid microtracing if possible
====== aduke1 (2009-03-19 23:45:05) ======

Note that this also seems to fix the 'can't walk inside dropships'-bug Mattn mentioned in the mailinglist.
Well, the patch wasn't intended to fix that, but at least I can discomfirm that bug for fighter_crash map :)
====== tlh2000 (2009-03-20 18:02:39) ======

i thought mike fixed that earlier on already - r23605? (the can't walk inside a craft bug)
====== aduke1 (2009-03-20 22:18:49) ======

Yep, he did :)
I saw his fix in the commit log but somehow didn't associate it with the dropship bug.
So I drew the wrong conclusion...
====== wilminator (2009-03-21 06:59:28) ======

Here's my additions to aduke1's patch:
* Defined an RT_NO_OPENING constant to replace the magic -1 in some functions.
* Created an RT_TraceOpening function to pull out redundant code.
* Simplified some of the data passed to the floor/ceiling finding functions.
* Streamlined the microstep trace skip test.
* Adjusted the minimum hight to skip the microstep trace to CELL_HEIGHT (16 QUANTs). I figure that we may want actors slightly taller than a human in size, like the bloodspider (?)
* Removed unneeded comments.
I will commit this tomorrow, provided I don't hear back anything bad.
====== wilminator (2009-03-21 07:00:03) ======

slight mods to the last patch
====== tlh2000 (2009-03-21 21:33:16) ======

can someone explain me why we call CMod_LoadRouting "after" we increase numtiles? what about this patch?

Index: src/common/cmodel.c
===================================================================
--- src/common/cmodel.c (revision 23632)
+++ src/common/cmodel.c (working copy)
@@ -1090,6 +1090,7 @@
CMod_LoadLighting(&header.lumps[LUMP_LIGHTING_DAY]);
else
CMod_LoadLighting(&header.lumps[LUMP_LIGHTING_NIGHT]);
+ CMod_LoadRouting(name, &header.lumps[LUMP_ROUTING], sX, sY, sZ);

CM_InitBoxHull();
CM_MakeTracingNodes();
@@ -1104,8 +1105,6 @@
/* now increase the amount of loaded tiles */
numTiles++;

- CMod_LoadRouting(name, &header.lumps[LUMP_ROUTING], sX, sY, sZ);
-
FS_FreeFile(buf);

return checksum;

====== aduke1 (2009-03-21 21:52:34) ======

Looks nice :)
I vote for 15 QUANTs (CELL_HEIGHT - 1) because opening_size < CELL_HEIGHT will *always* be true inside standard buildings.
Later to be replaced by some TALLEST_ALIEN_WE_ACTUALLY_HAVE constant.

Another thing I toyed with are the traces at 1/4 and 3/4 for diagonal connections.
Skipping them completely brings us down to 34s from 41s. So it is worth to spend a few more thoughts here...

1. They are certainly overkill for 2x2 units because they only move half of their size.
So &#039;if (actor_size > 1) skip&#039; is the minimum we should do imho.

2. I&#039;d even vote for completely skipping them for 1x1 actors too. I know that it would be less accurate, but at that point we have already managed to shove a fullsize box horizontally through the opening. So we know there aren&#039;t any columns or walls we miss.
As a compromise:
Solution A: If the trace at 1/2 reveals an opening_base no more than LEGROOM higher than the two floors, skip.
Solution B: for diagonals, skip the trace at 1/2 and do traces at 1/3 and 2/3 instead.

====== aduke1 (2009-03-21 23:52:06) ======

@tlh2000 : CMod_LoadRouting() uses numTiles to mark parts of the added tile for re-routing.
This could of course also be done differently.
Is there a specific need/effect for moving that line or is it &#039;just for the looks&#039; ?
====== wilminator (2009-03-22 00:22:27) ======

@thl2000: The order of numTiles++ and CMod_LoadRouting is not important; but CMod_LoadRouting does need to wait for CM_MakeTracingNodes to be ran. I&#039;m including this modified version in my commit.

@aduke1 : I agree with your thought about the CELL_HEIGHT; I&#039;m switching back to your PLAYER_HEIGHT constant for now. I thought this value was already in QUANT units; I need to verify it.

Unfortunately, we cannot assume that we have the full opening assessed after the first horizontal trace. At most, it proves that there is a guaranteed opening wide enough to accommodate the actor for part of the opening, but the taller the opening is, the less accurate this trace is. At worst, we&#039;ve proven that a 1 QUANT slice is wide enough for the actor to pass. The additional 1 to 3 traces for floor ensure that the opening is wide enough for the actor to get between the cells, regardless of the size of the slice that succeeded earlier. A reason it might not is debris in the floor- the found opening may have missed reasonable sized chunks of (pick a substance) that an actor may not be able to get through without another trace through.

I also agree with your assessment of 1/3 and 2/3 traces for diagonals would help and still be effective. I also think that we need to look at what is really eating up our time and fix that. I may be able to remove one of the step traces in the microstep trace loop: I used to fill the value from the destination cell with that and I think we can get away with doing that again now that we can correctly project where the destination cell really is. Let me look into it further.
====== tlh2000 (2009-03-22 06:20:45) ======

as a reference: http://ufoai.ninex.info/forum/index.php?topic=3391.msg24281#msg24281

and yes - it looks ugly ;)

i would consider this a sideeffect which is never good imo. we should maybe use numTiles + 1 in the cmod routing loading and increment numTiles after loading everything - that would a lot easier to read and has less sideeffects.
====== tlh2000 (2009-03-22 07:02:39) ======

which reminds me of some other bug which might be pathfinding related - could on of you please have a look at the func_door issue? they are not placed correctly in the world (see e.g. the map +mart)
====== tlh2000 (2009-03-22 07:06:25) ======

r_showbox and sv_send_edicts might be cvars you find useful when debugging entity pathfinding (or -blocking).
====== geever (2009-03-22 13:00:58) ======

We have quite serious problems again. RMA is broken again, we can&#039;t access many tiles. Is it possible that the old bug came back due some version problems?

-geever
====== tlh2000 (2009-03-22 13:51:17) ======

are you sure that you recompiled all the maps?

and just a reminder for another "old" bug: we still can&#039;t enter trigger zones. As an example see the fueldump map. There is a gate with a trigger_touch in front of it (where the green smoke particle is located) - you have to collect the bomb from the hummer and lay it down there. But this is not possible as the movement is blocked by the invisible trigger_touch. So you can&#039;t enter the base.
====== geever (2009-03-22 14:06:23) ======

Yes, I&#039;m sure. Even I deleted farm/*.bsp and recompiled, and it still doesn&#039;t allow me to go onto fields for example.

-geever
====== keybounce (2009-03-22 16:58:18) ======

Regarding the value of numTiles and its incrementing:

How about a change? What if "numTiles" is always the number of loaded tiles, so that you always test from 0 to less than numTiles, and add in a new "curTile", for the current tile, used as an array subscript?

It&#039;s really, really distressing to see a global variable shared across three files, two of which claim to be "common", while the third is "server" (and probably all three are server), without a consistent invariant for its usage -- sometimes it&#039;s "number loaded", and sometimes it&#039;s "what we are currently loading".

====== tlh2000 (2009-03-24 07:37:33) ======


====== tlh2000 (2009-03-24 07:37:45) ======


====== tlh2000 (2009-03-24 07:38:09) ======

enoug tus - but can&#039;t walk there
====== tlh2000 (2009-03-24 07:39:00) ======

can&#039;t walk close to the house? map bug?
====== aduke1 (2009-03-24 22:56:31) ======

2.3 will NOT have 2x2-units, right ?
So I assume we will set ACTOR_MAX_SIZE to 1 for the release version, right ?
I did that before, several weeks ago, and it halved the CONNCHECK time as I expected back then.

For a completely different reason, I did it again today (based on rev 23685 NOT including your latest patch !). Only to find that it brings down CONNCHECK time from 54 to 12s, which is much faster than the 19-20s we had in December&#039;s trunk.

So the biggest question that remains for me is: Is that fast *enough* for the multiplayer-RMA-timeout BTAxis mentioned in the mailinglist ?? If it is, we could move on to fixing the remaining bugs in routing/pathfinding imho and get back to 2x2 units after the release of 2.3.

@wilminator : when do you plan to commit your recent patch ? If you want ME to commit it, just say a word...
====== wilminator (2009-03-25 04:19:01) ======

@duke1: Right now we can&#039;t divide the CONNCHECK counter in half- the code as is only traces for 1x1 actors. To speed the tracing up, we need to get the two directions at once like in that one patch.

I&#039;ve testing a change to TR_BoxTrace that outright skips tracing beyond a found brush, eliminating excess calls. It brought the wilderness compile down to 44 seconds, which was at 46 with the changes you provided so far and down from 56 from when we first started. I&#039;m also sitting on an extreme patch that allows hinting- telling the function where the most likely place is to find a brush. It shaved of another 3 seconds when I was testing it, but it changes an awful lot of functionality to get the speed. I&#039;m waiting on that till after we commit.

I will commit tonight if the rendering is fixed :( I couldn&#039;t see what I was doing, so I waited until tonight to test my changes. Otherwise, I will post a patch and if you are confident in it, you can commit what we have.

And after this, if you want to bounce an idea around, feel free to email, chat, or post it. But also feel free to commit a change if you feel it is the right thing to do- I&#039;m just one man and I don&#039;t want to be the only one knowing what the code is doing! :D
====== wilminator (2009-03-25 14:36:04) ======

I just committed the code I have. I&#039;m going to start on making the trace work for both directions.

This is a brain dump so that I&#039;m not the only one who&#039;s following along:
We are already tracing for openings and floors in one direction. In theory, this will be the same opening coming back. There is really only one case where this will not hold true- when an actor actually falls more than MIN_OPENING. It might be possible for the actor to walk back under the floor he just fell off of, but we will know about this opening because of two reasons:
1) The passage tracing works bottom up, so we should have already found it, and
2) If the passage would be in the same cell, we ignore the opening, as we cannot have two floors in the same cell, and our defined floor tracing marks teh highest possible floor in a cell as the floor of choice.

So then we end up with four possible outcomes when we go to trace between two cells, keeping in mind that the cell trace works up:
1) There is no opening in either cell, so we skip the trace.
2) There is an opening for an actor to be present in both cells, so we trace for an opening between the two.
3) There is an opening for an actor in the current cell but not the destination cell. We trace for an opening. If there is one, then we have found a cell above the destination cell that the actor can be in, and use the data found as in 2.
4) There is an opening in the destination cell but not the current cell. However, if we transpose positions, we are looking at 3) again. Call the tracing function with transposed x,y coordinates and an inverted direction (dir ^ 1).

From here, we need to edit the RT_MicroTrace function to generate the inverse stepup value- the one for the opposite direction. After that, we can either call the RT_FillPassageData function twice (once with each set of data) or edit it to update both at once. I&#039;m thinking of calling it twice.
====== tlh2000 (2009-03-25 17:55:00) ======

@aduke1 : no, 2.3 won&#039;t have 2x2 units - we don&#039;t have animated models, particles, techs and so on.
====== geever (2009-03-25 22:55:18) ======

Hi,

I hope you can investigate the RMA problem I reported before. Quick loading worths nothing if we cannot access tiles.

Another issue: on my AthlonXP 2000+ (1666Mhz) 1G ram, Linux i686 (Debian Etch) with r23697 :

$ time make maps -j 4
./ufo2map -v 2 -nice 19 -extra -t 1 maps/alienb/a_hangar.map

---- filesystem initialization -----
Adding game dir: /usr/local/lib/ufoai/base
Adding game dir: /usr/local/share/ufoai/base
Adding game dir: /home/geever/.ufoai/2.3-dev/base
Adding game dir: ./base
using ./base for writing
[compile] maps/alienb/a_hangar.map

real 45m53.068s
user 27m51.112s
sys 0m8.381s


46 minutes for a single map! DAAAMN SLOOW. ;(

-geever

====== aduke1 (2009-03-26 00:30:54) ======

Great:) current trunk brings us down to 40-41 secs for fighter_crash (from 54s).

Quote "the codeas is only traces for 1x1 actors"
Arggghh...I overlooked the RunThreadsOn() line. Nice trap ;)
I will do something about that.

As for committing stuff myself: I will commit whenever I am *sure*, but I still feel unfamiliar with the code (NO, it&#039;s not my personality) and as you are "Mr. Pathfinding" , imho it&#039;s a good idea if four eyes look at the changes. So plz bare with me ;)

btw do you agree with the following change in RT_MicroTrace():
// start[2] = min (top * QUANT - 1, (max(z, az) + 1) * UNIT_HEIGHT); /**< Just below the passage ceiling */
start[2] = bottom * QUANT + 1; /**< Just above the bottom of the found passage */
It squeezes out another 1-2 secs here.

btw2: quote "feel free to email". Somehow it seems I can&#039;t email you via your SF-account (bounces). Is it ok if I contact you directly for things that don&#039;t fit in the tracker ? (I already have your email)

@geever :
There must be something terribly wrong with your system or the way you do it. I just compiled a_hangar in 317 secs on a 2.6 GHz intel single core. And that was even on M$ Windoze ;)
====== wilminator (2009-03-26 04:18:02) ======

@aduke1 : Yes, you may email me directly. You might also consider emailing me through the dev list, so our conversations can be archived and shared as needed :)
Yes, commit that change! It makes sense; please remove the commented code when you commit. Remember- we only commit C comments and not C++ comments; no // please.

@geever : There is a problem there. I don&#039;t know what it is right now, but I do know that you are not compiling the way that I am. I&#039;m just using the downloaded kit off the wiki, as opposed to following your directions. I do know of a problem with the RMA tracing code and the model retracting code, as I never correctly undid my reverse- tracing code for those. Let me see if there is some way for me to insert some debugging code so we can figure out what is dragging you down.
I&#039;m curious: I ran the forest RMA the other day, and it assembled in less than 10 seconds. How long does it take you? There are no models on the map; I want to know if it is the RMA tracing or the model tracing. When I run the mine map, it takes about 30 seconds to retrace.

====== tlh2000 (2009-03-26 21:11:59) ======

@mike: aren&#039;t entities like func_breakable handled by mins/maxs and forbidden list?

yes the trigger in the map fueldump isn&#039;t working - you can&#039;t enter the target zone as it blocks movement
====== tlh2000 (2009-03-27 07:26:35) ======

a little sidenote - if a brush or entity has the solid flag set to SOLID_TRIGGER, it should not block the movement - only SOLID_BSP should do.
====== aduke1 (2009-03-31 21:42:05) ======

@wilminator :
Just in case you didn&#039;t: you may find it useful to update to latest trunk, because Mattn and I managed to cut down the time for the LEVEL-pass of ufo2map to one third :)
====== wilminator (2009-04-02 04:13:42) ======

@aduke1 & tlh2000: Thanks for that! I&#039;ve been out with bad allergies the last two weeks, and haven&#039;t been much good for anything :P

I&#039;m hoping to have time this weekend to commit the reverse-tracing code.
====== wilminator (2009-04-06 05:21:59) ======

Here is the first pass of the back tracing patch. It partially breaks the pathing, causing jumping and keeping actors from going where they should be able to. I&#039;m posting this as is so we can "not completely break" pathing in trunk at any given time.
====== wilminator (2009-04-06 05:22:45) ======

Backtrace- round 1
====== aduke1 (2009-04-06 22:58:45) ======

I applied your patch and have to say: I like it :)
Unfortunately, I couldn&#039;t get it to work.
But at least I found three problematic areas:

1. You overlooked that my &#039;try to skip microtracing&#039;-patch was designed for *unidirectional* tracing. If micro is skipped, BIG_STEPUP and such will not be set for invstepup. Easily fixed in RT_TraceOnePassage().

2. In RT_UpdateConnection(), both calls to RT_FillPassageData() use &#039;z&#039;. That doesn&#039;t seem to be appropriate in case of eg. a BIG_STEPUP. I recovered &#039;az&#039; from stepup and passed it to RT_FillPassageData(), but it didn&#039;t do the trick :(

3. In RT_TracePassage(), for z == 0 &#039;lowceil&#039; will always be 0 and thus
if (lowceil - bottom < PATHFINDING_MIN_OPENING) {
will cause the connection to be impassable...

hth

It&#039;s too late here now for further investigations.
Good Night and Good Luck...
====== wilminator (2009-04-07 03:49:19) ======

@aduke1 :
1. This is done. I&#039;ve also relocated some of the code dealing with the stepup and such to only fire if the microstep code could have been used but was intentionally skipped. I also fixed invstepup when there is no passage.


2. Part of the catch (I hope) is realizing that if z and az don&#039;t match, we need to deal with the lowest step of z and az- one of those sides will be blocked. I think I have taken care of this; however the catwalk in the wilderness amp is still broken while descending the stairs. I think the error is in the tracing and not in the z/az calculations, though.

3. I have altered lowceil for now. This was originally meant to detect the ceiling below the floor of the adjacent cell. That logic is now defunct, and the code detected the ceiling of the *current* adjacent cell. I took out the comparison so the floor is found at z=0. This may have to be changed again.

====== wilminator (2009-04-07 03:51:10) ======

Backtrace- round 2
====== aduke1 (2009-04-07 23:19:24) ======

WOW !
Your latest patch is a huge step forward :))

Good news:
- i could walk everywhere I tested including stairs (didn&#039;t test much though)
- CONNCHECK is down to 14s (as opposed to 39s in trunk or 20s in your previous patch)
Either you have done more than you described or it&#039;s a nice sideeffect of the fixes :)

Bad news:
- I still got some &#039;odd&#039; pathes sometimes (not a biggie)
- something seems to be *terribly* wrong with TU calculation. I experienced negative TUs after walking, more TUs subtracted than shown at the cursor etc.

Sorry, didn&#039;t have time for investigations today. And btw, I&#039;ll be afk for the long weekend to come :)
====== tlh2000 (2009-04-08 17:53:36) ======

a big thanks from my side, too - i just recompiled all the maps in less than a hour and have to say that it works a lot better than the current one in trunk.

i&#039;ve found a few glitches in the africa map - i&#039;m able to walk into the solid brushes of the ufo. screenshots attached.
====== tlh2000 (2009-04-08 17:54:18) ======

can&#039;t walk upstairs (patch 2009.04.06)
====== tlh2000 (2009-04-08 17:54:41) ======

walk into solid (patch 2009.04.06)
====== tlh2000 (2009-04-08 17:54:54) ======

walk into solid (patch 2009.04.06)
====== tlh2000 (2009-04-08 20:42:38) ======

just found out that i can&#039;t move in the alienbase at all - this smells like a map bug to me, as i haven&#039;t seen something like that in any other map yet. can one of you maybe give me a hint on how to fix that? just start skirmish, select .alienbase from the menu and test it yourself.
====== aduke1 (2009-04-08 21:30:27) ======

@tlh2000 :
thx, but imho you shouldn&#039;t waste time to report PF bugs atm. wilminator and I know about several issues that are still in the code (which also cover the things you just reported). Once we feel that we have squashed all the PF bugs we know of, we will call for &#039;fresh&#039; bugs ;-) (if any).

@wilminator :
The catwalk prob is easily explained imho as long as you&#039;re talking about going from (133, 143, 3) to (133, 142, 2).
I get this data:
data at cursor XYZ(133, 143, 3) Floor(1) Ceiling(80)
connections ortho: (PX=79, NX=64, PY=79, NY=80))
connections diago: (PX_PY=79, NX_NY=64, NX_PY=0, PX_NY=79))
stepup ortho: (PX=0, NX=32, PY=0, NY=2))

data at cursor XYZ(133, 142, 2) Floor(11) Ceiling(96)
connections ortho: (PX=79, NX=0, PY=0, NY=85))
connections diago: (PX_PY=0, NX_NY=0, NX_PY=0, PX_NY=85))
stepup ortho: (PX=0, NX=0, PY=32, NY=0))

So the z-delta is 6. While there are just two stairs...
With the 2008 code and MIN_STEPUP 5, walking up may or may not have worked, but with MIN_STEPUP set to 2, no microtracing will help.
as for walking down:
The NY doesn&#039;t have the BIG_STEPDOWN bit set because we have MAX_STEPUP set to 4 !

==> the map is not modeled &#039;correctly&#039; in respect to our PF algo and the grid. Maybe we should ask Rich to change it a bit eg. add more stairs ?


====== aduke1 (2009-04-08 23:02:23) ======

@wilminator :
Just tested with minstepup=3 and maxstepup=6, but still couldn&#039;t walk down :(

@tlh2000 :
My previous post does not cover the alienbase thing (you posted while I was writing). Sounds odd.
====== wilminator (2009-04-09 04:25:15) ======

@aduke1 :
The catwalk works fine in trunk with the lower stepup. This issue is from our algorithm change. I will wrap my brain around it some more tonight.

@tlh2000 :
I&#039;m recompiling my maps to get trace files for the maps. I&#039;ll get back to you when I know more about this.
====== wilminator (2009-04-09 05:04:05) ======

@tlh2000 :
ufo2map is not finding the floor brush at level 1 in alienb/a_empty.map. It finds some of the other brushes, but I can&#039;t say why. It does find the floor in alienb/a_hangar.map, so I&#039;m wondering if it is a map setting?
====== tlh2000 (2009-04-09 05:37:35) ======

thanks - the aliebase bug was a mapbug - the floor tile had &#039;passable&#039; set.

@duke: please explain a little bit more what must be changed for the stairs - i will do it then. it would be cool if we could get the article http://ufoai.ninex.info/wiki/index.php/Mapping/Ladders updated in a way that we (the mappers) know where to look for when we try to fix the bugs.
====== aduke1 (2009-04-16 21:57:05) ======

@wilminator :
I just committed the &#039;trace only at 1/3 and 2/3 for diagonals&#039; stuff we discussed below.
It saves us another 10% in CONNCHECK :)
I hope that doesn&#039;t interfere with anything you have done meanwhile...

@tlh2000 :
Sorry, I&#039;m still uncertain what the requirements really are. Let&#039;s wait for the &#039;final&#039; version of pathfinding.

====== tlh2000 (2009-04-19 07:51:54) ======

so this patch is "complete" now? (see r24091)
====== aduke1 (2009-04-19 21:41:39) ======

I did some testing on figher_crash and wilderness.map. Works like a charm :)
CONNCHECK is down to 12s for fighter_crash.

I only found two minor glitches:
- a zig-zag path in the left room of the building close to the dropship on fighter_crash
- couldn&#039;t walk down the last 3-4 stairs of the catwalk on wilderness

So I suggest the following roadmap:
- let&#039;s fix the two issues above
- fix the &#039;odd ceiling values&#039;
- let me apply another speedup
- place a public call for *fresh* pathfinding bugs

====== tlh2000 (2009-04-20 04:58:55) ======

sounds reasonable.

most of the pathfinding is working ok here, too - i&#039;m testing africa and alienbase (the hangar map - via +alienbase skirmish) - they have minor issues, too (the walk into wall that i posted below for the africa ufo is present in the alienbase hangar, too - so i suspect this is the same bug, too).
====== aduke1 (2009-04-20 22:55:37) ======

zig-zag path on fighter_crash
====== aduke1 (2009-04-20 23:24:32) ======

Added a screenshot of the zig-zag path. Note that there is an opening in the ceiling above !

I also committed a fix for it (rev 24128).
The point of the fix is: if we have a BIG_STEPDOWN, we should NOT block the passage below, because routing doesn&#039;t distinguish between stepdown(where the blocking would make sense) and falldown (where it&#039;s deadly).

To approve the fix, just remove the lines I commented out with an ansi-comment in RT_UpdateConnection(). To disapprove, just remove the &#039;//&#039; ;)

And while you&#039;re in that function, imho you should also change &#039;dir&#039; to &#039;dir^1&#039; in the second pair of RT_FLOOR & CEILING in the two blocks above. I don&#039;t know how often it occurs or what bug it will fix, but it looks *very* wrong to me.
====== tlh2000 (2009-04-22 07:01:53) ======

sorry to bug again - but someone already looked at the trigger_* entities blocking movement, too?
====== aduke1 (2009-04-22 23:23:13) ======

@tlh2000 :
Sorry, but I have no clue WTF &#039;trigger_* entities&#039; are. Could you plz give me a pointer to some info/docs ?

@wilminator :
good news: I figured out what happens in the "last 3-4 stairs of the catwalk on wilderness"
bad news: if I am right, and we can&#039;t find a cute little fix, we might be in for a major redesign :(

Here&#039;s what happens:
Let&#039;s call the XY-loc of the last platform before the water &#039;B&#039;, and the next XY a little down the stairs &#039;A&#039;.
For the z-levels I will use numbers, like in "from A0 to B1".
As A->B is dir 2, so stepping down those stairs is the &#039;backtracing&#039; part, dir 3.

- A0 has it&#039;s floor at 13
- B0 has a ceiling at 16
- ==> NO opening. ==> no stepping up one level. And that&#039;s it for z==0. Proceed to z=1.
- A1 has a nice opening and MicroTrace() finds a floor at -3.
- so B1 has the same nice opening towards A1, but it does NOT get the flag BIG_STEPDOWN
- not to mention the A0 never gets the BIG_STEPUP

There doesn&#039;t seem to be an easy fix for that. It looks like a major design issue and might even force us to refrain from &#039;bidirectional tracing&#039;

On a sidenote:
What I don&#039;t like about the current implementation is the heavy intermixing of &#039;meaasuring&#039; (ie. tracing and such) and &#039;interpreting&#039; the results.
Like in FindOpening() returning the assumed new z of the actor. I&#039;d like to cleanly separate them.
Do you agree with that (medium-term) design goal ?


====== tlh2000 (2009-04-24 16:51:31) ======

@duke:

in the quake world everything exept the brushes (minus inline models) are entities in the world. a weapon is an entity, a func_breakable is an entity and so is a trigger_hurt. some entities like actors are blocking movement in a forbidden list. but some entities should not block the movement (they are invisible and are just there for interaction) - like the trigger_* entities.

in fact everything that moves or that can change or interact is a server side entity. (on the client side they are handled as localEntitiy (le_t) and on the server side they are edict_t&#039;s (and to confuse you even more the renderer has also a entity_t which we can forget at this point).

maybe the problem is in ufo2map that the routing table won&#039;t allow movement into the trigger_* entities - they are brushes that were converted to entities to interact with the world. they should be ignored while creating the routing table.

@wilminator : TR_BoxTrace has an interrupted comment - can you please have a look at that?
====== tlh2000 (2009-04-24 16:55:35) ======

oh and to make it even more complicated - a func_breakable will block movement until its shoot - then the actors can walk there... so we have a third group of entities - those that can change the behaviour of the routing handling.
====== nobody (2009-04-24 17:31:44) ======

@duke:
You&#039;ve just seen the one big issue I&#039;ve had with backtracing: the algorithm assumes that all z beneath have been seen, and everything is hunky-dory up to that point.

I had code in RT_TracePassage for aboveceil and below ceil; it was meant to handle this case. I have expanded the comparison in the trinary operator for lowceil to use the aboveceil value if the belowceil value is not big enough, allowing the trace to go through.

====== aduke1 (2009-04-24 20:39:27) ======

@tlh2000 :
Thanks for the explanations :)

I investigated a bit, up to the point where I saw a 60:40 chance that it&#039;s NOT a pathfinding issue *with* triggers but maybe a coincidence of triggers and pathfinding issues.

Didn&#039;t find any tracker item nor forum post about that issue ?!?! Imho we should have a separate entry for that...
====== aduke1 (2009-04-24 22:51:33) ======

walking through a rock
====== aduke1 (2009-04-24 22:52:56) ======

zig-zag is partially back
====== aduke1 (2009-04-24 23:02:29) ======

@wilminator :
While I am still trying to fully understand how the code works now, I also did some testing.
I can walk down the catwalk and wade through the water
But as Murphy says, one fix brings up at least two new bugs. *sighs*
(Two screenshots attached)

What about the other stuff I mentioned:
- the lines I commented ot with &#039;//&#039; (and Mattn immediately turned into C-comments ;)
- the &#039;dir^1&#039; issue in RT_UpdateConnection()
- the design goal ?
====== tlh2000 (2009-04-25 06:56:04) ======

wade throught? it looks like you are walking on the water... the water brush should be marked &#039;passable&#039;.
====== tlh2000 (2009-04-25 07:49:42) ======

about the trigger issue - i would say Grid_MoveLength returns ROUTING_NOT_REACHABLE - maybe the server would also allow to walk there - but the client turn the cursor into blue and thus we can&#039;t advise the actor to try it.
====== tlh2000 (2009-04-27 06:11:34) ======

can you please have a look at this:

http://ufoai.ninex.info/forum/index.php?topic=3519.0

i&#039;ve converted crouchingState into a byte as it can always only be 0 or 1 - but i&#039;m not sure about those checks there. was the conversion bad? do you need e.g. negative numbers somewhere?
====== aduke1 (2009-04-27 19:12:30) ======

afaik we only use 0 and 1.
I changed the asserts a bit in three places. If we ever decide to use more states, we&#039;ll have to look at many more places.
====== tlh2000 (2009-04-27 19:17:05) ======

thank you very much
====== aduke1 (2009-04-27 22:23:16) ======

I have just committed a few lines of code (rev 24253) that speedup CONNCHECK for eg. wilderness.map by some 33% :)

Plz note that I don&#039;t really like the place (RT_FindOpening()) where I had to put it in. Imho this is a different *strategy of tracing* and should be forked from RT_UpdateConnectionColumn(), but that would require quite a lot of refactoring and should be done after the release of 2.3.

Also plz note that it doesn&#039;t have an effect on those maps that have the &#039;odd ceiling values&#039;-problem. It does of course have a similar effect if I adjust the &#039;sky-height&#039; value to those odd values. So that&#039;s where to easily gain more speed...

@tlh2000 : You&#039;re welcome.

====== wilminator (2009-04-28 05:09:00) ======

Sorry, I&#039;ve been suffering from moments of sanity lately...
@aduke1 :
I think I just figured out the ceiling issue- the ufo2map routing code skipped tracing for cell floors and ceilings outside the bounds of the map, which used to include z directions. I&#039;m removing that bounds check in CheckConnectionsThread, which should make all sky-facing floors have a ceiling at PATHFINDING_HEIGHT*CELL_HEIGHT. Please let me know if this works.

Your patch is a great idea, however it fails if we ever create a hedge maze (which might be a cool map) or have a similar situation, like a fence with an entry arch. Any wall that had no ceiling on either side could not have a passage, as the opening would not be detected. Instead, we would detect the top of the wall as the bottom of the opening, ignoring any other actual openings in the wall. I will leave it here for now, as if we agree to never make a wall with a passage and no ceilings, then this does become very useful.

I am undoing your comments for the BIG_STEPDOWN because the code is needed. It sets the cell -below- the current cell as being unable to move into the cell you are about to step down into. Because the stepdown will create a corresponding STEPUP in the lower adjacent cell, the cell beneath the actor (the true adjacent cell of the current adjacent cell) should not ever reach the cell you are about to step down into. This code would impact steps that slope down from south to north or west to east and there was an opening under the steps, similar to the bottom of the catwalk in the wilderness map.

You are right about the ^1. I have added it. It will have no major effect on individual maps, as the default values of 0 prevent movement between cells. The big impact will be RMAs, where the retracing of a wall might not be corrected.

I agree with your design goal if we can reasonably separate the measuring(routing) and the tracing. The funny thing about tracing is that we already measure a lot so we can position the trace. I do not want to clean the code by running the calculations twice.

I guess a fair way to move forward with this is to describe my current overall process:
1. Look for places actors can exist in cells (Tracing part 1).
2. Look for ways actors can move into these cells (Tracing part 2).
3. Determine the constraints that actors have moving between cells (Routing).
4. Move an actor between cells (Pathfinding).
* Subject to change by popular consensus

2 and 3 are currently jumbled, but I don&#039;t see a nice way to split them. As soon as we know the size of the opening, we can describe how small an actor can be to use an opening, and after we microtrace, we know how much the actor must be able to step up to get into the next cell. Most of our contorted logic is to skip as many traces as we can. Splitting that out might not be a bad idea.

One last thought I had- what if we converted the floor and ceiling to be absolute from the base of the map, instead of relative to the bottom of each cell or the floor in the current cell? In the routing code, it would remove a lot of (z * CELL_HEIGHT) stuff. The trade off might be where we use the relative floor and ceiling to determine where we can take shortcuts, so no more RT_FLOOR()<0, we&#039;d use RT_FLOOR()<z*CELL_HEIGHT.

And again, thanks.

====== wilminator (2009-04-28 05:14:47) ======

I had at one time considered turning crouchingState into actorMovementState, which would check on crouching and flying (since you can only do one of walk, fly, or crouch at a time).
====== tlh2000 (2009-04-28 19:29:56) ======

the actorMovementState conversion seams reasonable with the description you gave below.

which reminds me: please try to use camel case variable names. i&#039;ve started to convert some vars a few days ago, because our code is mixed by int this_is_a_var and int thisIsAVar (the former should be only valid for cvar variables)
====== aduke1 (2009-04-28 23:20:41) ======

actorMovementState:
I actually did think of that. But the fix is merely a change of 3 lines and I volunteer to revert/adjust it as soon as we have fliers ;)

skyHeight:
I tested it: you fixed it. I closed it :)

&#039;entry arch&#039;:
Hehe, you&#039;re very good. I actually ran into exactly the prob you described in the 1st version of my code, found out by testing and fixed it. If you look at the code a tad closer now, you&#039;ll find that the &#039;skycheck&#039;-block *only* returns if the opening_base is not higher than cell-floor+MIN_STEPUP. In all other cases we proceed with &#039;guaranteed opening&#039;.
I also added a comment stating that (r24273).

BIG_STEPDOWN:
Hmm...not sure. I hope your other fixes compensate for that. We&#039;ll see once I can test again (battlescape is currently broken).

dir^1:
Great. You found out what my suggested fix actually fixes: the is a bug post in the forums about blocking along the borders of maptiles in RMA. I *bet* that&#039;s it !

design goals:
I see we are thinking in the same direction :) We can slowly but surely (and very carefully) move in that direction. I&#039;m still looking for the best place to discuss some details...
For now I understand the primary goal is to fix the remaining bugs and release 2.3.

absolute height:
Yup. We have *6* ways to express the height of a given point on the map: mappoint, quants and level; each relative or absolute. This is surely a *big* part of our problem. It&#039;s confusing and thus error-prone.
I&#039;m not sure if storing absolute height values will solve *all* those problems. Another approach might be to calc everything in mappoints and store the results as needed. Not sure though. Let&#039;s find the place to discuss that first...
What about a patch-tracker-item without a patch titled &#039;refactoring routing&#039; ?

roadmap:
In addition to the little roadmap I lined out some pages below imho we should check the known issues before calling for fresh bugs. Looking at all the bug-items that are assigned to &#039;wilminator&#039;, I&#039;d suggest I go top-dowm and you go bottom-up ?



====== aduke1 (2009-04-28 23:38:27) ======

Oops, almost forgot:
Qoute: "And again, thanks."
You&#039;re welcome. It&#039;s a pleasure for me to work with you and I&#039;m learning a lot in the process :)
====== wilminator (2009-04-29 04:38:37) ======

@aduke1 :
BIG_STEPDOWN:
That code is more insurance rather than functional- it forces all &#039;walkable&#039; paths to be reversible; eg if I can walk there, I can walk back. This is, of course, lost if the actor has to &#039;fall&#039; any distance (the drop is larger than their stepup), but I am trying to prevent an actor being able to walk into a cell, but then try and walk back and ends up in a different cell. In theory, we shouldn&#039;t need to call that code anyway because the opening below would be blocked anyway, but I wanted the insurance.

@tlh2000 :
I&#039;m pretty certain at this time that there is something else wrong happening besides submodel tracing in regard to triggers. I&#039;m dropping all sorts of debugging code in, and the issue I&#039;m finding is that the triggers are not firing at all. I walk on the bomb and nothing fires. I think that the trace is picking up the gate model, and not the gas, and that is what is blocking out the "extra" cells. This needs its own ticket now, as it is quickly becoming a "not routing" issue from what I&#039;m seeing. And if it comes back around as a tracing issue, we can deal with it then.

With everything that&#039;s been said, I think then we are ready to call this part of the patch committed and done. I agree that we should quickly review the tickets in the tracker and see if we can identify any recent glaring issues and then issue a call for fresh bugs. I&#039;m closing this ticket and agree that we should open a couple of new tickets about the actorMovementState concept (so we don&#039;t lose it), the RMA bug to ensure that it is fixed, and the trigger issue.
====== Missing Comment Alert ======

The importer failed to retrieve a comment in this thread. Please view the old ticket link above for full discussion details.