speed up terraforming

[Dwachs]

Here is a quick-and-dirty patch for speeding up terraforming enterprises: Instead of the current recursive approach, it fills a list with potentially affected tiles iteratively. Then this list is used for the checking whether terrraforming is allowed. If yes, then the list is taken to do the actual terraforming.

The speedup is tremendous: just create a hill in the sea with trunk version and patch version I could create a mountain +21 z levels above sea level within milliseconds.

The patch is for raising only. The AI functions ebne_something are broken as well.

Please test & comment.

A full patch will probably be not massive. As much code can be reused for the lowering operations.

[kierongreen]

Interesting approach, will test tomorrow

[Markohs]

extending the ctest on current code to cover nw,ne,se and sw is not possible? Because I have the intuition it should maybe render the same cost savings, that's where this rutine it's losing performance I think.

Yep, this code certainly needs speedup, making big hills is one of the slowest operations in game.

[Dwachs]

extending the ctest on current code to cover nw,ne,se and sw is not possible? Because I have the intuition it should maybe render the same cost savings, that's where this rutine it's losing performance I think.

The problem with ctest is that it prevents the algorithm back to the tile it came from, but it does not prevent it to go to the previous tile again during the recursion. Tbh I was surprised that this ctest approach worked at all

[Markohs]

Yes, it can go back because on sw,se,nw and ne the ctest is reset to 15 again (all directions), let me check if using ctest on corners works, it should, testing...

So many files changed since my last compilation that I need to re-create the project again.

[Markohs]

In fact, I think the ctest values are incorrect right now, on sw corner it passes "11", binary "1011" , that's a strange value (previous to DOUBLE_HEIGHTS), this needs fixing, let me see...

[Markohs]

It works, and it's at least as fast as your solution, maybe more because it doesn't need to generate the list I think (works on the structure itself and never goes back).

Code Select Expand


/* raise plan
* new heights for each corner given
* only test corners in ctest to avoid infinite loops
*/
const char* karte_t::can_raise_to(const spieler_t *sp, sint16 x, sint16 y, bool keep_water, sint8 hsw, sint8 hse, sint8 hne, sint8 hnw, uint8 ctest) const
{
    if(!is_within_limits(x,y)) {
        return NULL;
    }

    grund_t *gr = lookup_kartenboden_nocheck(x,y);
    const sint8 water_hgt = get_water_hgt_nocheck(x,y);
    const sint8 h0 = gr->get_hoehe();
    // which corners have to be raised?
    const sint8 h0_sw = scorner1(ctest) ? (gr->ist_wasser() ? min( water_hgt, lookup_hgt_nocheck(x,y+1) )   : h0 + corner1( gr->get_grund_hang() ) ) : hsw + 1;
    const sint8 h0_se = scorner2(ctest) ? (gr->ist_wasser() ? min( water_hgt, lookup_hgt_nocheck(x+1,y+1) ) : h0 + corner2( gr->get_grund_hang() ) ) : hse + 1;
    const sint8 h0_ne = scorner3(ctest) ? (gr->ist_wasser() ? min( water_hgt, lookup_hgt_nocheck(x+1,y) )   : h0 + corner3( gr->get_grund_hang() ) ) : hne + 1;
    const sint8 h0_nw = scorner4(ctest) ? (gr->ist_wasser() ? min( water_hgt, lookup_hgt_nocheck(x,y) )     : h0 + corner4( gr->get_grund_hang() ) ) : hnw + 1;

    const sint8 max_hgt = max(max(hsw,hse),max(hne,hnw));

    const uint8 max_hdiff = grund_besch_t::double_grounds ? 2 : 1;

    if(  gr->ist_wasser()  &&  keep_water  &&  max_hgt > water_hgt  ) {
        return "";
    }

    // more than 4096 calls => might need a screen update ...
    if(  ((++raise_frame_counter)&0x0FFF) == 0  ) {
        INT_CHECK( "simworld.cc" );
    }

    const char* err = can_raise_plan_to(sp, x, y, max_hgt);
    // sw
    if (err == NULL  &&  h0_sw < hsw  &&  ((ctest&11)==11)) {
        err = can_raise_to(sp, x - 1, y + 1, keep_water, hsw - max_hdiff, hsw - max_hdiff, hsw, hsw - max_hdiff, 11 );
    }
    // s
    if (err == NULL  &&  (h0_se < hse || h0_sw < hsw)  &&  ((ctest&3)==3)) {
        const sint8 hs = max( hse, hsw ) - max_hdiff;
        err = can_raise_to(sp, x, y + 1, keep_water, hs, hs, hse, hsw, 3 );
    }
    // se
    if (err == NULL  &&  h0_se < hse  &&  ((ctest&7)==7)) {
        err = can_raise_to(sp, x + 1,y + 1, keep_water, hse - max_hdiff, hse - max_hdiff, hse - max_hdiff, hse, 7 );
    }
    // e
    if (err == NULL  &&  (h0_se < hse || h0_ne < hne)  &&  ((ctest&6)==6)) {
        const sint8 he = max( hse, hne ) - max_hdiff;
        err = can_raise_to(sp, x + 1, y, keep_water, hse, he, he, hne, 6 );
    }
    // ne
    if (err == NULL  &&  h0_ne < hne  &&  ((ctest&14)==14)) {
        err = can_raise_to(sp, x + 1, y - 1, keep_water, hne, hne - max_hdiff, hne - max_hdiff, hne - max_hdiff, 14 );
    }
    // n
    if (err == NULL  &&  (h0_nw < hnw || h0_ne < hne)  &&  ((ctest&12)==12)) {
        const sint8 hn = max( hnw, hne ) - max_hdiff;
        err = can_raise_to(sp, x, y - 1, keep_water, hnw, hne, hn, hn, 12 );
    }
    // nw
    if (err == NULL  &&  h0_nw < hnw  &&  ((ctest&13)==13)) {
        err = can_raise_to(sp, x - 1, y - 1, keep_water, hnw - max_hdiff, hnw, hnw - max_hdiff, hnw - max_hdiff, 13 );
    }
    // w
    if (err == NULL  &&  (h0_nw < hnw || h0_sw < hsw)  &&  ((ctest&9)==9)) {
        const sint8 hw = max( hnw, hsw ) - max_hdiff;
        err = can_raise_to(sp, x - 1, y, keep_water, hw, hsw, hnw, hw, 9 );
    }
    return err;
}


Do you want me to implement it for lower too and commit to svn?

The idea is that recursion is:

east recursion recurses east
west recursion recurses west
north recursion recurses north
south recursion recurses south

sw recursion recurses sw, but *can* spawn one south and another west.
nw recursion recurses nw, but *can* spawn one north and another west.
...

So it never visits a tile twice

[Dwachs]

So it never visits a tile twice

This will not work, sometimes hills will flow around a corner. See attached savegame, raise the upper-most tile.

[Markohs]

Whats suposed to happen? Worked here, I don't get where the problem is.



patch, ignore the changes outside the function because are not aplicable.

[Dwachs]

That looks right ofc. I did not test your proposed change.

Maybe your description was not correct?

east recursion recurses east
west recursion recurses west
north recursion recurses north
south recursion recurses south

sw recursion recurses sw, but *can* spawn one south and another west.
nw recursion recurses nw, but *can* spawn one north and another west.

With this description the algorithm would never reach the tiles directly southeast of the raised tile.

Edit: please test again with attached savegame ...

[prissi]

Great, I wanted to do this for ages but got distracted by other stuff. Considering the time it needed before, any solution is better! Thank you very much.

[Markohs]

Well, I missed southeast and northeast and did put "..." just to type less. But yes, ofc that happens too.

EDIT: woops, the station was eaten! Let me check what was wrong.

[Markohs]

I see what's wrong, raise tool makes ramps with 1 height difference, but using slope tools height differences of 2 can exist, so created ramps by the tool can propagate backwards, destroying this artificial slopes, and that needs to be avoided.

I *think* my modified algorithm can be fixed to take care of that when detects height differences  of more than 1, but well.

Since you have a new algorithm working (I've tested it), that even adding complexity and being not so easy to read and understand makes a huge performance difference, it certainly makes it worth incorporating it.

You were right.

EDIT: Anyway I'm trying a new aproach, I find the raised grid point and I iterate the sourounding plans in concentric tile squares, I check all tiles for the feasibility of raising them at center - radius. Once I find a square completely sunken under or at the exact requested level, or find a not raisable tile, I have the answer.

[Dwachs]

Here is the final patch

[TurfIt]

Now that's more like it   Where was this a couple days ago when it took me 15 mins to raise a level32 hill... Now < 5 secs!

As an extension request - is it possible to relocate movingobjs on the affected tiles instead of blocking the raise/lower?

[prissi]

I would first suggest to commit this before asking for extensions (as usual). Adding movingobj should be not too difficult though.