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. _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
