glob2-devel
[Top][All Lists]

## Re: [glob2-devel] Pheramonal-Directional Algorithm

 From: Martin Voelkle Subject: Re: [glob2-devel] Pheramonal-Directional Algorithm Date: Sun, 6 Nov 2005 16:28:57 +0100

for those that dont' know what pheramonal-direction algorithm is look at Alleyways, and pathfinding and Lokadin's posts mainly

- I think your pheromone-based algorithm can work, but I'm afraid it will take
even more memory than the actual gradients. Could you do some estimation for
a typical map? It would be nice because it would make a starting point to
discuss the algorithm in more details and it would help us to be sure that we
have all understood it.

note: I haven't actually had a chance to look through the specifics of the current wavefront but I mean there are only so many ways you can do a wavefront

okay so lets see say a large map is 128x128 that is 16384 or 128^2
now each wavefront has one byte for it's value (i,e closeness of path) and i'm assuming it uses another variable for type (so as not to have to make many maps)
and three players say for your average map
every byte has 8 bits
so
128^2*8*2*3 = 786 432
0.8 mb

k now with pheramones we use same map 128^2
now we have say pheramones(short, 2 bytes),direction (1 byte) and type(1 byte) that comes to a total of 4
and we need one pheramone map per player so times 3
128^2*8*4*3 = 1 572 864
1.6 mb

so okay, it uses twice as much ram :S i guess lol. but I mean 1.6 mb isn't all that much, i'm sure graphics and other things spend a lot more. and gradients put a lot of load on the processors as you have to recalculate them a few times a second and pheramoens don't really have to ever be recalculated.

Like i could be all wrong about this whole calculation thing but I mean it seems to make sense, anyways it's actually 03:30 so i'm just gonna go to bed

- I've been working a bit with ant biologists those last two years. Of course,
ants uses pheromones, but:
- ant solve congestion (up to a certain extent of course) by climbing on each
others, they live in 3d not 2d.

unfortunatly i don't think we can't do that :(

Pheromones seem a good way to go because they scale computation-wise. Why did Nuage and NCT decide to drop the pheromones used in Glob1 (if I'm not mistaken) to use gradients in Glob2?

Some local congestion problems can be avoided if globs are allowed to cross each other. Also if faster globs have higher priority, they can force a slower one to go back a position, provoking a cross between both globs. Imagine a faster glob (F) and a slower glob (S) going in the same direction on a 1 lane way. F goes twice as fast as S.
F S
FS
FS
Now, F can't advance. But if it waits one step, S will have to move. If F chooses its next cell first and both globs can cross each other, F will take S's place and S will have to go back. The end result will be that F has exceeded (is this the right word?) S:
FS
SF
S F
S F
...

Martin