http://aigamedev.com/open/tutorial/clearance-based-pathfinding/
Is there a java implementation of this, or any pathfinding that allows for different sized units instead of 1 per tile? A unit that takes up 4 tiles (2x2)? And the unit is not necessarily a square unit, they maybe rectangular for example taking up 2 tiles (1x2).
I’ve got A* down, but I need to figure this out (more explanations also help)
How about treat that 2x2 tile as 4 1x1 tiles? and so for the rest sizes.
M-m-m-m-multiple maps!!! It would take some pre-processing of each map, however you can build several versions on the same map, each one tailored to a specific ‘size’ of unit.
Then, when a creature moves, it searches the map constructed for its size. If you’re worried about a dynamic map (creatures cannot overlap/move through each other at any point) then you just make sure that each logical tile in your game knows which map tiles it belongs to. When an entity moves over one, you update each map tile to say that it’s overlapped.
Depending on your target platform, the size of the maps, etc, this might be over kill in some way, but iit’s possible that it’s faster than trying the 2x2 or 3x2 or whatever each time.
Did you read the link? The whole point of clearance based pathfinding is to only store one clearance map that can be used with A* to calculate a path for a suitably big/small object.
counterp: was there anything specific you were having problems with? The clearance based A* seems relatively straightforward (the hierarchical stuff… less so. 
)
Derp. I fail. I blame the fact that I’m currently trying to reply to things/read from my Android phone. >.> I should probably actually read/notice links.
I didn’t quite understand how to set a clearance value for each tile for starters, (1, 2, 3, 4, 5, etc) so I thought looking at a java implementation would help
@ReBirth not sure what you meant
Treat a big tile as some small 1x1 tiles.
It’s explained at the “The True Clearance Metric” bit. Basically for each tile you find out how far right and down you can extend it without hitting an impassable tile. That width/height is the clearance value.
problem is I have an ‘infinite’ map, is the only way to keep recalculating each time a new area has been discovered?
You mean a 2x2 tile as 4 seperate 1x1 tiles? but how would that even work
Fy, rom what’s been said, I think I understand the problem (Yay!), but I still haven’t actually read the page yet (I’m just responding/talking through my little phone while I try to make a section of my house wheel chair accessible.)
Anyway, it seems that for an arbitary sized/shaped map (let’s call it that, instead of infinite) that you have a few options.
Recompute the clearrance when more areas becoming visible.
Compute the clearance as soon as you can. However, this let’s the path finder sort of “see beyond” the sight area of the creature when picking a route (the pathfinder gets the clearance values, which indicates open spaces, meaning it’ll know where the creature can fit before it gets close enough to see.)
Attempt to disable the clearance path finding through unseen areas. Not sure how to accurately do this though.
Make a maximum limit on the clearance value of each tile (the smallest you can, and still fit your largest creature). Then, instead of recomputing each time you discover an area, you just mark a ‘seen’ flag, if it’s seen, then you get it’s actual clearnce values, if it’s unseen you get it’s unseen values (preferably either the maximum-- so that your path finder will assume that any sized creature can move through an unseen path-- or some arbitrary other value.) Still has the issue that the path finder can see a bit beyond the edges of the creature’s vision (tiles on the edge of vision in certain directions with give information about what’s further in that direction).
If you give us some idea about what you’re trying to do: how you’re genetrating your map, whwther vision matters (sort of assuming from what you said), etc. We might be able to give you an answer to better suit your needs.
Woah, clearance map are so simple and easy, I absolutely love it
My first idea would have been to regroup 4 1x1 tile together and do some fancy iterating through it but the clearance map idea is so much more elegant and probably faster.
If I was you I would stick to square unit. It will make your life easier. Even if the unit is square you can make it look like if it is rectangular. Most RTS do it this way; some unit have recrangle graphic but when you test their collision detection it’s obviously square.
It should relatively simple to make rectangular units work. Keep X & Y clearance seperate, then have an internal variablein a unit that states whether it’s rotated/oriented along some axis. Your path finder would have to know whether how to change the orientation to fit, but all in all that should only increase the number of possible nodes by a rather minor number. (Whether turning would count as an action/costly operation when the path finder searches is up to you.)
Yes I just thought of #4 yesterday and all is going well. I’m just gonna finish making it work with rectangular units and all should be well.
Thanks for pointing me in the right direction guys
Well here is a graphical demo - completely unoptimized (didn’t even merge clearances with node class, and new nodes are generated each time a path is found instead of saving them), possibly not even working properly, I don’t feel like thinking for a while.
http://www.java-gaming.org/?action=pastebin&id=143
By default the unit size is 2x3
Thanks again, feel free to point out any flaws, and you may tell me any suggestions for optimization (I already have a couple of ideas)