[glob2-devel] Globule pathfinding

[MOA3333]

There are some older emails about this. I will continue my brainstorming
on this subject. In the past emails, i thinked splitting the gradient in
regions is good. It can help with speed, but it is both hard to code and
with problems related to the border betwen regions.

In order to eliminate this problems, regions should take as much as
possible the shape of obstacles. Folowing this idea, i have found that
the best should be to eliminate completly the gradient algorithm. Each
obstacle is a region, each region is an obstacle.

The new algorithm if it works, should be able to know a path to any
region/obstacle, not the best, but one that is good enaught. This means
it will at best know the average distance to the target, and it will be
very difficult to know exactly witch building is closer.

First, the base algorithm: 
  - identify each obstacle as a region: it must be of a single type
  (wood, building, weet, etc) and must be continous, a single piece.
  Each case will have a number that is the same as the region, and i
  don't know yet if a type representing the region is useful.
  - apply an algorithm that will compute all free spaces that are near
  each region, at distance 1, then 2, etc,  like in the gradient system,
  but starting with all the regions at the same time. The idea is that
  each free case should belong to a single region, the closest, and not
  try to cover the hole map. Finaly the hole map is covered, but each
  case with the gradient of a single region
  - Other diference from the gradient system, we can keep in each case
  other informations, not only how far it is from the building. One
  information should be in witch direction the closest region is. This
  can be one of the 8 directions (or a more precise direction, like a
  range of integers???)
  - Other infomration we can keep is witch case of the region is (or was
  when the gradient was first computed)) the closest. We can put numbers
  on the border of each region this way, and this is important.

This algorithm is a very human one, and can replace the fact that ants
can see. Actualy, globules can see the obstacles here. The clasical
gradient algorithm thinks that globules should take the closest path by
surfing on a line, taking a line.

This algorithm thinks that globules should go directly to the building
if they are near the building. If not, the globule must avoid obstacles
and then go to the building. To avoid obstacles, it will travel in a
cercle around each obstacle, even if it is closer to take the corner. 

The globule must be able to do the folowing:
  1 - go straight into the region that is the closest.
  2 - go away from that region into the oposite direction
  3 - go round the obstacle clockwise
  4 - go round the obstacle reverse clockwise

For example, a travel can be the folowing staps:  3242423242421, or more
general ([3 or 4] 2)* 1

The only problem is to decide a list of 3 and 4 to folow on the fly if
possible...

First way, the stupid one:
 - try to find the border of the region that is the closest to the
 destination.
 - go 3 or 4, depending witch is faster (we cana also consider haw large
 the road is)
This will be easy to implement, but it is not sure it will find a good
path, however it will always find a path suposing we do not have a
labyrinth.


Seccond way, a better one:
 - each region has a few neighbours. How do we know witch is the
 neighbour? Simple: when the gradient of two regions touch each other,
 then they are neighbours.
 - if we put numbers on the border of the region, than every border will
 have a neighbour and only one. (some time 2, but we ignore that for
 now)
 - a graph can be built, each region with his neighours and information
 about witch part of the region is closest to that neighbour.
Two regions that touch each other are NOT neighbours, and it is better
to consider a region only by the border that is possible to travel
along, not the regions that are not accesible.
 - Now we can apply a simple A* or somethink on this graph. A* starting
 from the destination, or even a gradient system on the graph, not on
 the map directly.



Optimisation: We consider a region of more than one type. This means
each region will realy be a region surounded by spaces. This will
simplify the problem related to regions that touch each other. This
means the destination will not be a region, but only the border of a
region. Globules will travel ([3 or 4] 2)* [3 or 4 ] 1

Optimisation2: We conider a single region all part that are separated by
a single case. Actualy this means globules will not be able to travel
there, but this is  a good idea since this will produce congestion. It
is up to the player to make space, especialy if bigger maps are
possible. It will be possible in the future to implement a function (5)
that means traversing a region, not by going round, but by going inside
a thin hole like this. This should be however used carefuly. 
Globules will travel (([3 or 4] 5? 2)* 1.  And the difficulty will be a
list of 3 and 4, eventualy a 5.

This is not yet the best, but it is what i have found for now. I hope it
is not too complicated. If you find the idea good, maybe a more simple
solution is possible. Actualy i think the graph will not change that
much, only localy. And the gradient we will be able to regenerate more
localy, ond only once from time to time.





-- 
http://www.fastmail.fm - A fast, anti-spam email service.