Re: [glob2-devel] understanding pathfinding

[Leo Wandersleb]

Hi Jannis,

nice you want to work on glob2. Concerning the path-finding, I clearly remember
having written something on the issue of one wide gaps. The according image is
still in the wiki [1] but the page is missing. Also I'm surprised that the image
is attributed to Kieran as I'm sure I did it. Hmm ... maybe it was on the
mailing list. Strange.
The more I think about it, the less I think, it would be anywhere near trivial
to solve this issue. On the phone I tried to explain my concept of such passages
to switch to one-ways but now I hit another problem:
imagine a passage with units wanting to walk past that passage entrance. They
might want to enter the gap and leave it at the same end just to avoid an
oncoming unit. Another unit entering at the other end would block them even as
they would never meet in the gap.
I guess there would be easier spots for optimization. Maybe the
hot-spot-gradient for idle units that we briefly talked about.

On the other hand, path-finding is rather a minor issue in glob2's struggle for
survival. Bringing out Beta5 would be much more crucial for the project as a
whole ;)

Regards,

Leo


[1] http://globulation2.org/wiki/Image:Oneways.png

On 26/03/11 11:27, Jannis Froese wrote:
> Hi,
> 
> I am a german student (18 years old) and will go to University in October.
> Currently I have my last exams at school and work as software developer. I
> really enjoy playing Glob2 and am looking a bit into the source code in my 
> spare
> time, perhaps contributing when I get the time.
> 
> Because when playing the game I had problems with traffic jams and "stupid"
> behavior of globules on 1 block wide roads, I wanted to check out how
> pathfinding works. I understand that this is a really time-sensitive feature
> because every globule has to use it all the time. As far as I understand the
> code, you are barely using the A* algorithm (only for warriors?) but mostly
> using the function Map::directionByMinigrad (I suppose speed issues?). It 
> would
> be nice if somebody could give me a few hints how this function works.
> 
> The funtion is using the two (constant) arrays tabFar and tabClose and is
> relying on gradients. What are these arrays for and how exactly work these
> gradients (which seem to be extremly important for pathfinding in Glob2).
> 
> Regards and thanks in advance
> 
> Jannis Froese
> 
>  
> 
>  
> 
> PS: You should change the welcome-message to this mailing-list. It still says:
>>New ideas should be discussed on the forum or in glob2-ideas and then posted 
>>as
> wishes bug in the bugtracker.
> It should instead point to glob2.uservoice.com for new ideas. 
> 
> 
> 
> _______________________________________________
> glob2-devel mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/glob2-devel