Re: [glob2-devel] my experiments on pathfinding and gradients (huge)

[Andrew Sayers]

Before we talk about gradients, I've remembered some of the more
important things I need to ask you about...

First, the random map generator.  Could you tell me a bit about how it
works?  It seems to be based on quite a complex algorithm - is it
something you made yourself, or based on known ideas?  If it's your own,
could you explain some of the theory?  If it's someone else's, could you
give me some information I can use to look up explanations?

Another more important thing is that the island and random map
generators don't work - any maps created with them will exit with a
failed assertion within a few seconds of starting.  I've not been able
to trace the source of the error - is this something you can easily fix?

Also, you use perpendicular iterators in some places - for example, the
"deltaOne" array in Map.cpp.  Is there any particular reason for the
order of iteration?  If so, (how) would the algorithm generalise to an
iterator of arbitrary length and width?  (I ask this so I can write
such a general iterator)

Anyway, on to gradients...

* resource gradients:

Sorry, I wasn't clear about this before.  As I understand it, only one
gradient gets updated each tick, and all gradients are always completely
remade.  I think we agree that this is inefficient in many cases.  My
idea is to continue updating one gradient per tick (for the most part,
at least), but to provide a list of recent updates so that when a
resource comes to be upgraded, it can decide whether a full rebuild is
really necessary.  The only case I'm currently tackling is that if all
the recent updates are convex, the gradient can be updated in a far more
efficient way.

Destroying a building is a good example of a convex change - all
gradients can be easily updated by propagating values from squares
adjacent to the building.  If the only change to a resource map between
two updates is that a nearby building was destroyed, this should only
trigger a minor alteration of the current gradient map, not a complete
remaking.

* Optimisation

You're right that STL-style iterators don't magically speed the code up,
but they do enforce better programming practice, and make the code
easier to manage.

For example, the gradient update algorithm was using index-based
iterators rather than pointer-based ones.  Changing that over lead to a
significant speed increase.  With an iterator class, a pointer would
have been used automatically.  By requiring the whole program to use
an iterator class, we can ensure that the right type of iterator is used
for every iteration in the program.

At present, the best tool for iterating over the whole map seems to be a
pointer, but if it turned out there was an even more efficient solution,
you would only need to change the implementation of the iterator class,
rather than every instance of every iterator in the whole program.

Another benefit of an iterator class is that it's much easier to debug.
For example, I've found it's a surprisingly hard problem to make sure an
iterator does the right thing when it goes past the end of a column or a
row.  With an iterator class, you only need to get this right once, and
write a single test suite, then the rest of your code can just rely on
it to be correct.

Could you talk me through the process of checking processor usage?  It
seems that Engine.log shows you the percentage of the time the processor
spent at each level of use.  Can it go above 100% like the load bar in
the game itself?  Also, do you have to play through a whole game before
it will tell you the processor load, or is there some way of quitting
halfway through?

* last change

You're right about my off-by-one error, thanks for checking.  I've now
committed your change.  I must admit that I only understand pockets of
the current code - the ideas are often excellent, although the
implementation lacks in places.  I've rewritten a lot of it from scratch
in the map-rewrite branch, to try to keep the good parts and get rid of
the bad.

        - Andrew