[http://sourceforge.net/p/ufoai/patches/394 Item 394] imported from sourceforge.net tracker on 2013-01-28 20:34:58

This is NOT a patch.
It's merely a demo of a design concept for Wilminator to look at.

The idea behind it is quite simple:
32 mapunits are equivalent to some 1.3 meters. Very few soldiers on this planet (not sure about aliens ;) ) do that in just one step. So we can safely assume that we can climb at least 2*STEPUP as long as there is something suitable to step ON between target and origin.

This demo lacks (at least):
- I didn't care for the correct setting of brushesHit
- there may be more aspects to stepup_height in Grid_MoveMark()
- didn't really know how to check for a *horizontal* thing to step on
- couldn't remember a map with a decent slope to test with

The disadvantage will be that ufo2map will take an estimated 15% longer due to additional boxtraces.

Sorry that I couldn't deliver a complete patch, but I'm currently preparing for a loooong holiday :)))

However, on the fighter_crash map, even this demo seems to work nicely :)
===== Comments Ported from Sourceforge =====

====== aduke1 (2009-01-06 00:25:55) ======

part 1
====== aduke1 (2009-01-06 00:27:03) ======

File Added: routing.diff
====== wilminator (2009-01-06 06:49:14) ======

It is a good concept patch. I may adopt it, depending on how much of an improvement I can't squeeze out of the hinted tracing functions I am working on. I'm including the patch of the step solution I currently have written.
====== wilminator (2009-01-06 06:49:56) ======

Microsteps patch
====== aduke1 (2009-02-10 23:49:44) ======

I'm back from a much too short 4-week holiday :(((
- updated from SVN
- found an incredible increase of speed (feels like down to < 10% of the old map loadtime) Congrats :)
- scanned the logs
- didn&#039;t see a commit of the &#039;micro-step-code&#039;
- saw some entries in the mailinglist, but unsure if it was about &#039;micro-step&#039;

I assume the attached patch does no longer apply. So what&#039;s next ?

====== wilminator (2009-02-11 06:32:29) ======

aduke1:
Welcome back!

I&#039;m having issues finding time to finish this patch as quickly as I would like, so I am going to post what I have for now for posterity.

I&#039;ve had to rethink the whole tracing process used to determine the routing data. I implemented a version of the microcode, but discovered that the quick-checks I implemented were eliminating good path options and making maps impossible.

My new strategy is to try to find a path down, then if there is no path down, then try to find a path up. The only thing I don&#039;t like about the new tracing code is that there is no longer a "short circuit" trace- I now need to trace every nook and cranny looking for an opening, which could be annoyingly time consuming. Later, I was thinking of making the trace_t type return the actual impact location so that the tracing code could scan more intelligently, but this will have to do for now.

The only thing that is incomplete at this point is the "new" RT_FillPassageData, which is supposed to run a final check on the various values for obvious "these heights don&#039;t work" conditions and then updates the RT_CONN and RT_STEPUP values in both directions.

None of this code is tested in its current state. Individual snippets still work, but the RT_TracePassage_r is completely new, and other peices of code have been adapted to the new tracing model. The actual micro-step code does work very well based on my previous use of it.

Please not that this patch is cut off of SVN 21851. I haven&#039;t been updating to ensure that my code would work, and there may be issues when applying it to the current trunk.
====== wilminator (2009-02-11 06:34:12) ======

Current (Broken) Stepup Patch
====== aduke1 (2009-02-11 22:17:08) ======

Hmm... your description of the current status isn&#039;t very encouraging. Sounds like a whole lot of additional boxtraces :( Somehow I feel that there must be a more simple way to do it.

I&#039;ll have to clean up my own working copy before applying the patch.
Meanwhile...:
How did the 2.2.1. code detect staircases ??
I glanced at the 2.2.1 code weeks ago in order to find out, but had no luck. Searching for several keywords (pathfinding, routing etc.) brought up nothing. Can you give a hint where to look ?

====== aduke1 (2009-02-14 23:20:47) ======

I managed to apply your patch to rev 22622 without big problems, just a merge conflict in cmodel.c. I even think I understand some parts of it ;)

The first test brought up an assert in RT_FillPassageData(). A little debugging showed that it&#039;s because &#039;opening_base&#039; is not initialized nor set.

If I understand the code correctly, it should be set to the &#039;bottom&#039; value that is calculated by RT_TracePassage_r(). So we merely have to transport it out of RT_TracePassage(). Is that correct ?




====== wilminator (2009-02-15 07:30:17) ======

That is correct- the opening_base value is the bottom value found in RT_TracePassage_r.
====== aduke1 (2009-02-16 19:56:53) ======

Good news:
I added the aditional parm and it compiled a map.

Bad news 1:
It took 13,230 sec for the CHECKCONN part (plus 30s for the rest). It took me some debugging to find out that it was NOT an infinite loop. Guess we&#039;ll have to tune it a bit. I&#039;ll see what I can do...

Bad news 2:
When trying to start the map, I got this:
==== InitGame ====
********************
ERROR: CMod_LoadRouting: Map has BAD routing lump; expected 18874392 got 18874374
********************
Note the difference of 18. Strange. Any ideas ?

====== aduke1 (2009-02-16 20:37:57) ======

Found it. The length calc was way off, adding the i from the for-loop. Probably a merge problem.

Now I can load the map, but pathfinding is broken. Soldiers are walking around in crazy patterns. Investigating...
====== aduke1 (2009-02-16 22:55:21) ======

Update:
In RT_TracePassage(), the &#039;end&#039;-vector was not initialized. As a compensation, the &#039;start&#039;-vector was initialized *twice* ;)

Good news:
After correcting that, the map compile time for fighter_crash.map went down to some 1200s (still a long way to go...) and the pathfinding works again :)

Bad news:
I can&#039;t enter buildings on that map AT ALL :(
====== aduke1 (2009-02-18 23:52:15) ======

Good news:
I replaced RT_TracePassage_r() with a completely new algo.
- map compile time is down to 98s (still a bit slow, but I see some &#039;reserves&#039;)
- I can enter buildings again

Bad news:
Still can&#039;t walk up stairways :((

To be continued ....

====== aduke1 (2009-02-20 22:58:59) ======

After fixing a bug in my new RT_TracePassage_r(), map compile time went up to 245s again:(

The reason for not walking up stairways is not in routing, it&#039;s in pathfinding ie. Grid_MoveMark():
actor_stepup_height = PATHFINDING_MAX_STEPUP;
[...]
if (height_change > actor_stepup_height) {

in defines.h we have:
#define PATHFINDING_MIN_STEPUP 3
#define PATHFINDING_MAX_STEPUP 5

So it&#039;s pretty much the old known problem...

My question is: if MIN_STEPUP now restricts the height of one microstep, can&#039;t we set MAX_STEPUP to a much higher value ???

I&#039;ll attach a copy of the new TracePassage_r(), you&#039;ll get the idea.

File Added: TracePassage_r.c
====== aduke1 (2009-02-23 23:34:08) ======

Gotcha :)
I found a shortcut:

/* First prepare the two known end values. */
bases[0] = max(0, RT_FLOOR(map, actor_size, x, y, z)) + z * CELL_HEIGHT;
bases[steps] = max(0, RT_FLOOR(map, actor_size, ax, ay, az)) + az * CELL_HEIGHT;

/* shortcut: if both floors are not too far below the bottom of the opening, we can skip microtracing */
if (bases[0] >= bottom - PATHFINDING_MIN_STEPUP &&
bases[steps] >= bottom - PATHFINDING_MIN_STEPUP ) {
*delta_h = max(0, RT_FLOOR(map, actor_size, ax, ay, az)) + az * CELL_HEIGHT - max(0, RT_FLOOR(map, actor_size, x, y, z)) + z * CELL_HEIGHT;
*opening_base = bottom;
*stepup = 0;
*invstepup = 0;
return top - bottom;
}

This brings CONNCHECK down to 30s and pathfinding still seems to work nicely.
Unfortunately, I didn&#039;t take note of how long it took before (on my ooold pc).
But I think it&#039;s even faster now.

Imho this is the point in time where we should commit what we have to the trunk and then start fine-tuning. What do you think ?

====== wilminator (2009-02-25 04:35:25) ======

I&#039;m looking over your changes- I&#039;m thinking you may have a more workable solution than I do right now. Please send me a full patch file of your changes and I will give it a one over. I&#039;m thinking that the only thing I don&#039;t agree with completely is the "big box" part- a better test might be to center the box between the two cells and scan using the actor&#039;s size. This would address an issue of actors not being to move diagonally when a post is immediately on one side.
====== aduke1 (2009-02-26 00:32:27) ======

Ok, here&#039;s the patch of what I have based on rev 23021.
When I wrote &#039;pathfinding works nicely&#039; I was wrong :( There are still (at least) 3 issues:

1. Standing in front of a stairway in a building. Floor = 1, ceiling = 16. The new TracePassage_r() calcs opening as 8 (should be 9, but that&#039;s a minor problem).
GridMoveMark() refuses to move because 8/9 is not enough for an upright actor (11).
You can crouch up the stairs, though.

2. Standing on the highest part of the stairway, you can&#039;t walk to the next floor. Opening is calculated correctly, but FillPassageData() doesn&#039;t set the RT_CONNs correctly.

3. Not sure if I completely understood your point regarding the &#039;big box&#039;. Imho lowering the box that spans two cells to detect the highest obstacle is very efficient. For orthogonal connections. However, looking at the code again I noticed that for diagonal connections a &#039;huge box&#039; is created (spanning 4 cells) which is NOT what I intended and most probably leads to wrong results.

I think I know how to get around #1 and I have to completely rethink #3. So I&#039;d suggest that you focus on #2 where I&#039;m a bit clueless atm...

P.S.: In addition to what&#039;s described below please note that I also changed some z to az in the part below az++ in RT_UpdateConnection() !

File Added: 2009.02.26.stepupDuke.diff
====== wilminator (2009-02-26 05:43:09) ======

Number 3 is what I was talking about, and is the biggest problem (tracing headache kind): TR_BoxTrace will take an extent box (bminis, bmaxs) and slide it from start to finish, indicating a collision if any brush hits the extents box while being moved. Unfortunately, we cannot (easily) take a rectangle and rotate it to scan through unless we want to extend a function like TR_HintedTransformedBoxTrace to work for all tiles in a loaded map. Right now, it is used only by the breakables collision code to rotate the breakable before tracing.

I&#039;m releasing what I have so far before I wipe and load your patch. I&#039;ve gone back to the drawing board again, realizing that I was trying to optimize too much to get good results. I have reverted back to a single trace in each direction, and accepted that some traces will done twice, because there is no clean way to mark what has been traced before, especially in game when linking tiles or accounting for breakables. The major change here is that I am now intentionally tracing for the lowest available passage, and then deciding if moving through it will cause my actor to rise or sink a game level.

The tracing code becomes very familiar (to what I had before we started to try and fix the stairs issue) and can possibly be optimized with some of your ideas: there are two scenarios. The first scenario is that the ceiling an floor are close enough that there is a certain block cannot have any brushes in it at all is there is to be a usable opening (based on PATHFINDING_MIN_OPENING). If this trace finds something there, there is an impassable obstruction. If not, the opening is scanned up ward and downward using a binary split algorithm to determine the top and bottom of the opening. This is considered a passage if the total opening is at least PATHFINDING_MIN_OPENING. While the most traces to find the bottom is 3 for the floor and 8 for the ceiling, this takes possibly too many traces. But, if we borrow your item 3 idea and run a normal box trace half way between the start and end, we can use the lowest floor and ceiling found to find the top and bottom of the opening. The only time there might be discrepancies is on the diagonal traces, where there will potentially be some ceiling or floor obstructions not found, but relatively speaking, this is currently about 13% of the space trace by my algorithm, and 0% error on the normals. Doing four more traces (at the 1/4 and 3/4 points) would reduce the diagonal error to 7.5% possible error.

The second scenario is if the ceiling is too far from the floor to have a guaranteed space. Currently, I have the function trace a 1 QUANT slice at a time looking for an opening. If found, the function uses the same opening search function to find a ceiling. If the found opening is not tall enough, the slice traces restart one QUANT above the found ceiling. While this could take 16 traces (up the side of a cliff) to find nothing, the function will know if it has an opening within 9 traces. And if we adapt the thought I had about a trace up the midpoint, we can find the ceiling in one trace with 13% error or three traces with 7.5% error. I do want to point out, though, that since the area required to be a floor is so large compared to the actors, we might not miss anything.

I will have to look into item 2. It will get us whichever code we put into play.

Again, thanks for your help on this. My life has been crazy lately, and I&#039;m trying to get this in so we can release!
====== wilminator (2009-02-26 05:45:36) ======

Wilminator routing patch (defunct)
====== aduke1 (2009-02-27 20:14:19) ======

1. Imho we shouldn&#039;t go back to unidirectional tracing. I actually love your semi-ingenius way to do it. Going back would double all tracing for connections at once. So let&#039;s keep it and put RMA aside until we found a nice way to initialize the routing table.

2. I really like your suggestion to use a box of actor-width halfway between start and end. That is almost as safe as my 2-cell-box for orthogonal dirs and good enough for diagonals. It would also solve the problem #1 (first step of a stairway).

3. Be careful with binary tracing. If I read your TR_TracePassage_r right, it was very efficient on even ground with NO obstacles, needing just a single trace. But as soon as there is some debris on the ground, it takes 8 traces to find the opening. And it took 31 traces to find out that it&#039;s standing in front of a wall !!

So if you could only fix the problem #2 in FillPassageData, I&#039;m convinced that we will have working code again :)
====== aduke1 (2009-02-27 21:00:00) ======

Ooops...until right now I didn&#039;t notice that your latest post also contained a new patch.
If you consider what I suggested in my previous post, should I even take a closer look at it ?

As for RMA: atm we initialize the routing table to &#039;0&#039;. What if we used say xF0 instead, indicating &#039;not yet traced for&#039; ? Of course, we would also reset the borders of the assembled tiles in RMA to that value.
xF0 is high enough for the unsigned char values in routing_s (ie. stepup, opening & ceiling) to be out of range. And if we use -1 to indicate &#039;no floor&#039;, xF0 is also distinct from that :)

P.S.: please remove the &#039;semi-&#039; from &#039;semi-ingenius&#039; (translation problem).

====== wilminator (2009-03-05 05:55:41) ======

OK, here&#039;s my latest attempt at fixing this. I used duke&#039;s idea of finding floors and ceilings to try and replace many horizontal box traces with a few and to remove binary traces. The current version does not take advantage of bi-directional tracing, but I will put that back in as I see this working as we expect. The only issue I see is that I am creating the possible scenario where an actor with a big enough stepup could walk down an opening that another actor can&#039;t because of a limitation of our grid based positioning. It has taken me so long because 1) no time and 2) I had to get my head around the "what can go wrong" scenarios, which I think I finally get again.
====== wilminator (2009-03-05 05:56:21) ======

Another microstep patch
====== aduke1 (2009-03-05 22:34:42) ======

+ I applied your patch to rev 23286 without any problems
+ looked at the code and I guess I like the new design ;)
+ map compile is reasonably fast (65 s for CONNCHECK)
+ I finally understood what you meant by &#039;guaranteed opening&#039; ;)

- the &#039;BAD routing lump&#039;-error is still in the patch, but that was an easy fix
- a brief test with estate.map revealed that there is at least one more bug in the code (large areas are not reachable)
-- worst of all, I can&#039;t test/debug as usual because the devmap cmd is currently broken. Let&#039;s hope Mattn fixes it soon.

Question 1: Is there a specific reason why you decided not to use my little trick from my alternative version of TR_TracePassage_r() (ie. tracing just every 6th QUANT) in the &#039;brute force tracing part&#039; of your patch ? Did I miss something ?

Question 2: I noticed that the &#039;LEVEL&#039;-pass (building the bsp-tree) in ufo2map has become significantly slower (5-10 times ?) in current trunk code. Do you think that this is just the price we have to pay for the much faster boxtraces ? Or does it imply a problem ?

P.S.:
I withdraw my suggestion about RMAs in my previous post after a closer look at the RMA code ;)

====== wilminator (2009-03-06 02:00:47) ======

> - the &#039;BAD routing lump&#039;-error is still in the patch, but that was an easy fix

I though I fixed this with a full recompile of ufo2map, ufo, and the map I was testing.

> - a brief test with estate.map revealed that there is at least one more bug in the code (large areas are not reachable)

This may be due to the stepup value not being inserted into the bsp file. debug_croute and debug_sroute both work and I verified that the stepup values are not being inserted into the code (or at least correctly). Plus, I think I need to update Grid_MoveMark to use the new BIG_STEPUP and BIG_STEPDOWN bits.

> Question 1: Is there a specific reason why you decided not to use my
little trick from my alternative version of TR_TracePassage_r() (ie.
tracing just every 6th QUANT) in the &#039;brute force tracing part&#039; of your
patch ? Did I miss something ?

I missed that part! And it is a smart move- I would then need to trace down to catch additional passage space. I&#039;m adding that now.

Question 2: I noticed that the &#039;LEVEL&#039;-pass (building the bsp-tree) in
ufo2map has become significantly slower (5-10 times ?) in current trunk
code. Do you think that this is just the price we have to pay for the much
faster boxtraces ? Or does it imply a problem ?

> I don&#039;t think that&#039;s me/us. I haven&#039;t touched the tracing code in a long time, at least a month, and when I had last tested it, the code ran fast (1s on my Phenom, single thread). Right now the very end takes a while, total time is now 10s :(

I will post more later tonight; I have somewhere to be in 45 minutes :)

====== wilminator (2009-03-06 06:48:25) ======

OK, here&#039;s tonight&#039;s installment-

I&#039;ve put back in aduke&#039;s "6th QUANT" idea for both halves of RT_FindOpening, changing +6 to MIN_OPENING, as this is the largest jump that can catch an opening. It cut the connection trace time in half. :)

I&#039;ve also been revising the microstep code to ensure that it gives the desired results (at least in cell [153,151,3] of the wilderness map, your mileage may vary). So far, this is looking good, as it makes the required stepup 3 moving to [153,150,4]. Note that this area of the map is the transition from the cliff to the catwalk, and the stepup value is flagged to let Grid_MoveMark know that an actor walking this direction will rise a z level. I still need to fix that part of the code; it currently causes an actor to randomly hop, jump, and skip.

After we get this done, I will look over the level tracing code to find out why those last traces take forever.

====== wilminator (2009-03-06 06:50:29) ======

Incorporated +6 QUANT code
====== aduke1 (2009-03-06 23:20:06) ======

Yeah ! We&#039;re getting close...

+ no more &#039;BAD routing lump&#039;-error
+ good speedup for map compile
+ the &#039;hopping actor effect&#039; is quite funny for a while ;)

cmodel.c, around line 1760:
if (dir < CORE_DIRECTIONS) {
// const int stepup = RT_STEPUP(map, actor_size, x, y, z, dir) & ~(PATHFINDING_BIG_STEPDOWN | PATHFINDING_BIG_STEPUP);
const int stepup = RT_STEPUP(map, actor_size, x, y, z, dir);
if (actor_stepup_height >= stepup) {
// if (stepup && PATHFINDING_BIG_STEPUP) {
if (stepup & PATHFINDING_BIG_STEPUP) {
nz++;
// } else if (stepup & PATHFINDING_BIG_STEPDOWN) {
} else if (stepup && PATHFINDING_BIG_STEPDOWN) {
nz--;
}

You must have been very, very tired when writing this code *bg*

The above fix gets rid of the &#039;hopping actor&#039;, but unfortunately it also seems to prevent actors from stepping up one level :(
It&#039;s too late here today for more bugfixing ==> your turn ;)
====== wilminator (2009-03-07 06:21:20) ======

Tonight&#039;s work:
I believe that the ufo2map program is now correctly generating the needed data for this to work. However, I have found that CMod_LoadRouting is not correctly loading the routing data back in. I wrote in a check in ufo2map to ensure that the compress/decompress pair work correctly; atm they work correctly. I don&#039;t know what is causing the issue. To see what I mean, uncomment the RT_WriteCSVFile call in LoadRouting and look at z=7 y=154 x=128 in wilderness.walls.1.csv in the directory with ufoconsole.log and the wilderness.walls.1.csv file in the maps folder when you compile with -tracefile. Look for a row of 0-0 across the bottoms and tops of some of the cells in the game generated csv file that are not present in the compiler csv. This data mismatch is prevalent in the connection and stepup data in game, and is causign this to not work.

And you were right- I&#039;m up too late for this ;)
====== wilminator (2009-03-07 06:22:06) ======

ufo2map generates correct data, ufo fails
====== wilminator (2009-03-08 00:40:00) ======

I have discovered that there is some problem with the routing data being written to / read from file. I have added code to verify that the data is not overflowing the buffer, and provided dumps of the data being created and processed by the compress and decompress code. The only thing I can find is that at some point, the data becomes corrupt, and I don&#039;t ahve a good reason for it. I&#039;m posting what I have for now. ufo2map creates a src.in file in the ufo2map directory and ufo creates a src.out file in the ufo directory (usually the same for developers.) This is not good :(

====== wilminator (2009-03-08 00:43:27) ======

file data debugging, r_model.c fix
====== aduke1 (2009-03-08 21:49:58) ======

The problem I am facing here doesn&#039;t look like corrupted data:

On fighter_crash map, I can&#039;t walk inside buildings. I can walk one step into the building though. From that point, the openings in all dirs (except back through the door) are calculated as 16, which is wrong of course.
Probably as a consequence of that, the stepup values are 129 or 130 ie. have the BIG_STEPUP bit on. This probably screws pathfinding later on.

====== aduke1 (2009-03-09 23:27:36) ======

Found it :)))

In RT_FindOpening(), &#039;az&#039; wasn&#039;t calculated correctly. As we calculate the ceiling as 16,
temp_z = min(floor(hi / CELL_HEIGHT), PATHFINDING_HEIGHT - 1);
makes microtracing one cell higher as it should and render stupid results.

Did this:
temp_z = min(floor((hi-1) / CELL_HEIGHT), PATHFINDING_HEIGHT - 1);
... and could walk inside buildings again.

After also setting PATHFINDING_MAX_STEPUP to 6 (needed to reach the 2nd cell of a std stairway), I could finally walk the stairway and the 2nd floor again :))))

I hope the above fix doesn&#039;t break any concepts I may have misunderstood.
====== wilminator (2009-03-10 02:18:07) ======

The (hi - 1) looks good, and is the correct fix. We want the hi to round down in all cases. I&#039;m thinking of using temp_z = min (temp_z{after that calculation}, z+2) or something similar to lower the top of the microstep tracing, because the az value cannot be more than one higher than z (actors can&#039;t climb two cells in one step), so the highest we need to start scanning is the top of the cell above z.
====== wilminator (2009-03-10 04:44:07) ======

I added the (hi - 1) into the temp_z calculations like you asked for. I also removed my file debugging code. I figured it out- I had copied a maps folder in my personal settings directory and had a bsp file in it. This file had override on the bsp file I was compiling. I also added the cap on the initial height of microstep traces; it helped a little.

I&#039;m not happy with some of the routing quirks I&#039;m seeing when a cell has if&#039;s boundary right on a multiple of CELL_HEIGHT; on the wilderness map I can&#039;t walk over an entire section of land because of it. I will get that knocked out tomorrow.

Something to think about: If an opening is so high that it is impractical to use it on both sides, maybe we don&#039;t need to microstep trace it. I&#039;m now trying to optimize our code.
====== wilminator (2009-03-10 04:44:37) ======

Making priority 8- we need to get this done so we can release.
====== wilminator (2009-03-10 04:45:23) ======

Fixed ceiling issue
====== tlh2000 (2009-03-10 14:20:33) ======

once you are ready to commit the patch, please also add a reference to this tracker item. there are some nice information in here that i would hate to lose.

what are the remaining problems right now?
====== aduke1 (2009-03-10 23:47:00) ======

Problems:
1. The "LEVEL"-pass of ufo2map takes 10 times longer than in december&#039;s trunk. Just tested it, this prob is not part of the patch, it is already in the current trunk.
2. The "CONNCHECK"-pass of the latest patch takes more than twice as long as current trunk. There are several ideas to improve that. Note that this also affects RMA !
3. some unwalkable areas on at least one map (wilderness). Sorry, I can&#039;t debug wilderness.map due to broken devmap cmd. No clue how many other maps are affected.

ufo2map data for fighter_crash.map (trunk vs patch):
LEVEL 24 vs 24; CONN 23 vs 53; Total 70 vs 104 seconds.
Don&#039;t know if that&#039;s representative for the other maps...

So it&#039;s a classical tradeoff: speed(mapcompile,RMA) vs playability (stairs, bugs).
It&#039;s not at all up to me to decide that, but if you want my personal opinion: commit it *right now* and let&#039;s do the optimizing and fixing in the trunk.

One last thought: atm we can&#039;t use 2x2 units at all, right ?
Setting ACTOR_MAX_SIZE to 1 would leave us with half the time for both UNIT- and CONNCHECK and thus get us down to some 75s...no user would probably notice the difference.
That would give wilminator (and me) the time needed to apply the optimizations/fixing :)

====== wilminator (2009-03-11 02:58:55) ======

After I get the wilderness path issue straight, I think that most of the stairs issue will be fixed, and we can commit the patch. *Yay!* I think that we could have this in trunk soon, but every time I give a date, something comes up...

Note: I test the wilderness map by actually running single player skirmish. Wilderness is last on the list, so go back one.
====== wilminator (2009-03-11 05:17:25) ======

Tonight&#039;s edition:
Added function headers explaining what each new function does in preparation for trunk merge.
Got the functions in routing.c giving (relatively) correct values. The new headache is to finish adapting Grid_MoveMark to use the new data.
Removed the absolute height stepup check in Grid_MoveMark. Now you should be able to use the steps in the estate without bumping up STEPUP. In fact, you may be able to decrease it.

Known errors:
On the wilderness map, you can now climb one of the rock formations at the top of the cliff. Some areas that should be are accessible are not unless you climb on said rock from above.
We still cannot climb back up some steps on the catwalk.
I rediscovered the "I can&#039;t fall because I found an alien" error.

The errors preventing a trunk merge:
The pathfinding at the top of the cliff that prevents the actor from walking on the regular grass without climbing on the rock. Once that is fixed, the new code is as good and as broke as the old code, so I have no moral issues merging the codebase then.
====== wilminator (2009-03-11 05:19:08) ======

Dressed up functions, broken MoveMark code
====== tlh2000 (2009-03-11 09:56:30) ======

had a quick look at the patch and besides the routing stuff which i wasn&#039;t able to test yet, i have some minor suggestions for you:

you added some /* Verify */ if statements - and asserts inside these ifs. It would be better to use Com_Error(ERR_DROP, ""); here imo. The asserts are gone in a release version but the if statement would still be around without doing anything. That&#039;s why an ERR_DROP is prefered imo.

you&#039;ve added (routing.c ufo2map) CORE_DIRECTIONS / 1 - is that a relic or intended? if intended, please add a comment, otherwise i might fly over the code later and optimize that away again (and maybe break stuff with it)

====== wilminator (2009-03-12 04:09:35) ======

> you added some /* Verify */ if statements - and asserts inside these ifs.
It would be better to use Com_Error(ERR_DROP, ""); here imo. The asserts
are gone in a release version but the if statement would still be around
without doing anything. That&#039;s why an ERR_DROP is prefered imo.

Good point. I think I will do that. If that condition ever occurs in a map, we need to know about it.

> you&#039;ve added (routing.c ufo2map) CORE_DIRECTIONS / 1 - is that a relic or
intended?

It&#039;s intentional- it was /2 for the bi-directional tracing. I didn&#039;t want to remove it so I knew what to update when we get that back.

Sorry, no patch tonight. I&#039;m feeling ill and need some down time tonight.
====== wilminator (2009-03-12 04:10:22) ======

Note: Next patch WILL be committed by general consensus on the dev list. I will also post it here for posterity. :D
====== wilminator (2009-03-18 05:49:19) ======

Here it is! This has been committed to SVN as of 23584. Now on to the bug tracker. :P
====== wilminator (2009-03-18 05:49:57) ======

Final patch- committed