Re: [glob2-devel] Map.h, map.cpp and gradients

[simon schuler]

Still not everything clear to me.


Andrew Sayers wrote:

> (This is in response to everyone's questions, really)
>
> <gradients generally>
>
> simon schuler said:
>
> > Hmm, strange description, I think it's just a normal floodfill
> > algorithm.
>
> Sorry, my computational theory is a bit weak on this one, and googling
> for "floodfill" just gives me a lot of talk about graphics packages
> (which I now realise, yes, is the same algorithm). Do you have a good
> URL handy that explains the theory so I can stick a comment in the code?
Hmm, if I think about it, I'm no more sure that it's a normal floodfill. 
( I mess
up names sometimes, sorry). A normal floodfill doesn't fill in different 
values.
It's more like a breadth-first-search from more than one starting point.
http://en.wikipedia.org/wiki/Breadth-first_search
(My theory knowledge is also a bit weak concerning the names of the
algorithms, although I know the algorithms...)

> Actually, if you're good with standard algorithms, would you mind having
> a look at makeRandomMap()? (it's the last-but-one function in my new
> Map.cpp). The comments in the original code strongly suggest it's a
> standard algorithm copied from somewhere, but I don't know what the
> algorithm is. I've tried to explain the function as best I can, but it
> would be really handy to have a name for it.
>
> <Shadow gradients>
>
> > I like the Idea of shadow gradients, but it won't be easy to
> > implement. The main problem is, when you got more than one explorer,
> > they will most probably all go to the same place. And if they once
> > have reached the same place, they will never split up again. So it
> > will be worse than before.
>
>
> Yes and no - zeroing out paths as you go along them will make that
> harder, and I've thought about creating "dents" in the landscape around
> your globs. Nuage's idea of going in random directions could work too -
> I'd like to see how things go in practice before thinking out a cleverer
> solution.
Perhaps it will work, but you will have to update the gradient very 
often, if you
don't want the explorers in the same place.

> <Compound gradients>
>
> First, to answer Simon's general argument: the resources would be
> calculated exactly as they are now, the only difference is that the
> globs would calculate their own personal gradient based on more than one
> actual gradient. So for example, you can prefer to avoid danger to such
> a degree that you will only follow a resource gradient if there's no
> danger gradient in view.
OK, I think I misunderstood it.

> Hmm, sort of. Thinking about it, buildings should all have a danger
> gradient equal to their firing range (or 0 if they can't fire) plus 3.
> Also, workers should use the following compound gradient:
>
> forbidden_gradient*256*256*256 +
> (danger_gradient<4?0:(255-danger_gradient)*256*256) +
> resource_gradient*256 +
> shadow_gradient
>
> Here's an example that will try to deal with everyone's objections at 
> once:
>
> Say you have a worker that is trying to gather wheat. The only patch of
> wheat in the map is two squares to its right. Four squares to the right
> of that is a level 1 tower (so the wheat is the most distant square
> within its range).
>
> To his left is a water square (and he can't swim). The elevations for
> that are:
> forbidden: 0
> danger: 0
> resource: 0
> shadow: 0
>
> To his right is a non-forbidden patch of grass. Two squares to the
> right of that is a non-forbidden piece of wheat, and five squares to the
> right of that is a level 1 tower (so the wheat is the most distant
> square within its range):
> forbidden: 255
> danger: 1
> resource: 253
> shadow: 0
>
> Above him is a forbidden patch of grass, and immediately below that is a
> piece of wheat:
> forbidden: 254
> danger: 0
> resource: 254
> shadow: 0
>
> Below him is a spot he's never seen before:
> forbidden: 255
> danger: 0
> resource: 0
> shadow: 255
>
> The worker is standing on a forbidden patch of sand:
> forbidden: 254
> danger: 0
> resource: 253
> shadow_gradient: 0
>
> The other directions are blocked off by various obstacles.
>
> So, for the square to the left:
> 0*256*256*256 + (255-0)*256*256 + 0*256 + 0 == 16711680
> For the square to the right:
> 255*256*256*256 + (255-0)*256*256 + 253*256 + 0 == 4294966528
> For the square to the top:
> 254*256*256*256 + (255-0)*256*256 + 254*256 + 0 == 4278189568
> For the square to the bottom:
> 255*256*256*256 + (255-0)*256*256 + 0*256 + 255 == 4294902015
> And for the square it's standing on,
> 254*256*256*256 + (255-0)*256*256 + 253*256 + 0 == 4278189312
>
> So it follows the highest gradient, to the right.
I think I still don't understand. For me there is still the problem when 
you have a
map like this:
IIIIIIIIIIIIIIIIII I = forbidden
I...W............I W = wheat
I................I T = Tower
I................I . = Grass
I................I G = Worker
I................I
I................I
I...T............I
I........T.......I
I................I
I................I
I................I
I................I
I................I
I...G............I
IIIIIIIIIIIIIIIIII
(Hope you can read the map, you need fixed character width)
The worker will walk up, until he reaches the beginning of the danger 
gradient.
Then The squares above him have danger 1, the ones on the left and right 
of him
have danger 0.
So the squares on the left and on the right will have much higher values 
than the
ones before him. Then he will walk right and left forever. He will never 
get into the
danger gradients. He will also never get to the idea af taking the way 
right of the
towers.

Simon