The algorithm should do the job in onFrame and in onStart. in onFrame, it first fluidfills walkable tiles in order to find the edges (walkable tiles near nonwalkable ones). there are two kind of zones considered: one only ads walkable tiles which have at least two nonwalkable neighbors on opposite sides (of that tile). These are named narrow, the other kind doesn't have such tiles (non narrow). Also, zones with low number of tiles are narrow. After fluidfill done, it should poligonize results. For all the zones it will pick an edgetile first from the list, then it will ignore the list, and will just check tiles next to this first tile, walking around edges. If it can't add any more, and there still should be a number of edgetiles poligonized, it will pick another non checked from the edgetilelist. In such a case it would mean that a zone have more then one poligon (like if you have doodads in a big walkable area, the outline of doodad would be also part of the zone, but it would be a different poligon, then the outermost edge of the zone). Now the problem is that while fluidfill finds a zone nicely, poligonizations would recognizse more poligons (it seems), even in cases when there is only one. Basicly, i just say, when its drawn, there are gaps in the poligon, mainly in 45 degree edges but sometimes otherwise.

The code would be in the attachment. Its written in VC++ 2008, it is the modified code of the BWAPI exempla ai module. (ignore the huge amount of static memory required, later i modify it to dynamic if that works)


EDIT: the = operator was not redefined for vect2d struct, so some other operations like firstpoint=lastpoint messed up things a little. still some problems. it seems that conditions should be rewritten a little, plus restructured, so that when finding new links, first we find al lthe candidates, and if there are more then one, pick the closest candidate which is present in the zone. That would give some overhead too... tell me if you notice other problems.

EDIT: new version. picks candidates up in a list, then if more, filters out those not present in current zone, then it should pick the one, which makes the next link deviate from previuos lines (links') direction. There is alos one more problem for sure. usually, it lefts out the last point from the poligon from some zones. there is some other problems.

EDIT: now it works it seems, problem was that as i changed it to pick up candidates first rather then just pick one, i forgot to remove code which would immediatly flag candidates as already picked (even if just only one was eventually picked, all the would be nodes had been flagged picked). Try to find bugs, if you will. Next part should be poligon simplification, then slising up zones, and in the meantime creation of pathes for zones. Poligon simplification is easy; you could throw in some ideas about how to slice up zones into "corridors","crossroads" or open areas, so, that it would limit the number of cycles. Now one idea at this point, is to just make a vary degraded version of those poligons, and check every link for every link. Pick the one which is closets, presents the same inner side to the currently checked, plus is the closest in angle (so as close to paralell as possible). I don1t know how much weight to give to those attributes. distance is measured from one endpoint of link. thats it so far. the pathing stuff in BWTA (which i want to replace at this point) Builds up Voronoy diagram for that. I want to make something faster then BWTA.

you should BWAPI from google code, if you want to check.

Attachments:

Post has been edited 6 time(s), last time on Nov 8 2011, 10:12 am by matefkr.

i think its fine for now, next i gonna make it dynamic memory then move on. could you check for other errors?

I noticed that there are buffer overflows.
You are checking the bounds, but it doesn't actually get checked until after the array is already read (and overflow already occurs). You need to check the bounds first.

I shortened some of it, and took out BWTA and extra stuff that were from the initial example module. Feel free to take what you like. I did not test it or even check to see if it compiled, but it should definitely give you some ideas for a better algorithm (at least one with not so much repetitive code). Hopefully you can fix that global variable issue that causes a uselessly large file size.

[attach=8218]

You should make functions for things so that there is less code to manage.

EDIT: Also, it's polygon*.

Attachments:

Post has been edited 1 time(s), last time on Dec 12 2011, 5:37 am by Heinermann.

ok thanks. next would be to reduce that file size, though i stopped working on it for a while. i gonna resume from time to time.

Attachments: