Re: [glob2-devel] New unit allocation system almost done

[Bradley Arsenault]

On 3/24/07, Kai Antweiler <address@hidden> wrote:
> > I've also implemented something completely new. In the code, I've
> > added something called "hidden forbidden areas". These areas act
> > exactly like forbidden areas, except that they are not visible or
> > modifiable by the user. They are strictly for the use of the Engine.
> >
> > I use these hidden forbidden areas in two ways. First of all, any unit
> > that is spinning on the spot automatically puts forbidden zone on
> > itself. These units are spinning because they have collided paths with
> > other units in narrow alleys.
>
> Warriors also spin when fighting.  Take care that they run away from
> there victims.
>
> When a glob is surrounded by resources it also spins.  Putting a
> forbidden zone under it could be a waste of cpu.  Nuage once told me
> that forbidden gradients are only calculated on demand.
> I don't know whether he meant that it is calculated when a
> glob is on a forbidden field or when the forbidden fields change.
> (The later would be a bug since resources can grow in forbidden areas
>  and block paths.)

I've looked into this. What I've observed is that forbidden ressource
gradients don't recompute if none exist, saving a small ammount of
CPU. Also, a unit getting trapped is no big deal. One square of
forbidden gradient should cause the algorithm to quit quickly with its
completed gradient. Forbidden gradients aren't even close to a bottle
neck. I highly doubt that even under heavy usage where we arranged the
forbidden zones just right for maximum cpu usage, it still wouldn't go
above 1% for the entire game.

> > While this may thoerietically cause some problems,in practice, units
> > only spin on the spot for more than a few frames when there is a
> > serious clog. And I have seen this code actually dissipate clogs. I
> > haven't seen any noticable negative impact on pathfinding.
>
> I don't like this, but go along.
> In the long run I would like to have this dealt by the an extra
> pathfinding routine, maybe oneways.  Leo also had an idea
> somewhere on our roadmap - I think.  Forbidden zone exiting and
> resource pathfinding don't go along well.

I considred this an option, but It invvoled allot more coding and
expanding of ideas. My first thought that the pathfinding should be
able to go "into" a group of spinning globs, but not go from a
spinning glob to normal path. This would cause the gradient to form a
path arround spinning globs, and it would also channel spinning globs
out of their current situation. However, I didn't want to modify the
actual gradient algorithm, because they are heavily optimized
algorithms that work on a generic "gradient"

> Systems that have problems in theory will get buggy.
> Things you took for granted won't be correct anymore.
> i.g.: when you have a narrow path where one side are forbidden
>      zones, a glob on a hidden forbidden field will be allowed
>      to path through that forbidden zones and do so when there
>      is a glob before and behind it.

I don't think this is something I took for granted. I never form one
wide narrow paths on purpose, they clog way too easily. And units
still take the fast route out of a forbidden zone, so they won't go
through the forbidden zone thats on either side when it has a non
forbidden right next to it. Even with all of the units spinning,
filling up the entire gap, the chances that they will disperse to the
edge is unlikely.

Even with all these conditions set, and they do start to disperse to
the edges, the gradient will be recomputed promplty and they will
return to the center because the hidden forbidden area was removed and
the center is the shortest route.

> > I've also implemented hiddden forbidden zones on buildings that are
> > being upgraded. When you start an upgrade, and the building is waiting
> > for units to clear the area arround. Now, the game automatically puts
> > hidden forbidden zone in this area.
>
> Can globs inside the building still get out of it?
> Do you place these areas also when the upgraded building won't be bigger
> than the original building?
> Why do you want these forbidden areas to be invisible?
> I think in the building case, the user should know what is going on.

Globs can still get out.

These are placed on all buildings going under construction. However, I
looked for myself. the values are ignored by the algorithms anyhow
because they are on a building, making slowdown almost none existant.

Well its possible to make the forbidden areas visible, I don't like
the idea that they can be modified by the user, or an AI like Nicowar.
I'm merely re-using existing code for a new features. I'll admit its
not the cleanest way of doing things, but in this case, it works, and
it works well. The structure is also simple and rather maintainable,
nothing particularly complex. Its just not a clean design.

> > I've tested Nicowar on a FourSquare modification where all of the
> > enemies are fully enclosed in wheat. With the new unit allocation
> > system. Nicowar successfully digs each of the enemies out and destroys
> > their bases. Warriors don't get caught up in the narrow alliess, and
> > enemies can't hide inside their ressources. Its very effective.
>
>
> Improvement suggestion:
> Does it go for teams that already have lost, too?
> Does it dig out buildings that don't have any free field next to it,
> like those overgrown inns from ainumbi?
> In both cases it better should not.

No, it goes for the team that its currently "targetting". It takes out
one team at a time.

Well yes it can make that mistake. There are many things the algorithm
could do better, for example, if Nicowar itself is dug in, it will
carve an almost straight line (arround stone) between itself and the
enemy, possibly through allot of unnesseccarry ressources. I might try
to make is so that it minimizes the amount of ressources it clears,
but that could become expensive to compute. I'm gonna try and improve
its placement of clearing flags, maybe even make it able to dig out
itself when some of its buildings don't have contact with others.



> --
> Kai Antweiler
>
>
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel


--
Really. I'm not lieing. Bradley Arsenault.