i'm generating tile based collision and astar maps based on the radius of the entity in question.
entities still occasionally collide with obstacles (clip a corner).
on the astar map, i'm going to have to "grow" all obstacles by the entity's radius to keep them "far enough away from the walls", right? and the size of a square should be the diameter of the entity?
and on the collision map, i don't grow the obstacles. and the size of a square is again the diameter of the entity, right?
Are you generating grids purely for AI purposes? And what do you mean by astar map and collision map - what's the difference?
If an entity's diameter is less than the width of the grid square, then by definition any path through empty squares that are adjacent is fine because the square is never narrower than its width. Obviously if you attempt to move from one square to another one diagonally then you're no longer passing through adjacent squares and you will (potentially) clip corners.
Sounds about right. You can also have single tilemap of your smallest unit type, but each tile then holds a 'clearance' value.
https://aigamedev.com/open/tutorials/clearance-based-pathfinding/
Are you generating grids purely for AI purposes?
yes
you attempt to move from one square to another one diagonally then you're no longer passing through adjacent squares and you will (potentially) clip corners
this seems to be the issue.
one solution i saw was to increase the radius of all obstacles enough so diagonal movement would not trigger a collision - leading to two maps, one for collisions, and one for pathing with somewhat larger radius obstacles.
so are there any other options available besides:
1. clearance based
2. enlarging obstacles on the astar map
3. no diagonal movement
how does "clearance based" compare to "larger" obstacles for implementation complexity? as i recall, when considering options, clearance based didn't sound that straight forward. its a two step check, itsn't it? and the assigning of clearance values, can that be easily computed automatically on the fly for on-demand real-time map generation? or is it more suited to hand edited level maps?
i suppose "no diagonal" followed by path smoothing is also an option.
if the size of an astar tile was sufficiently larger than the size of an entity, diagonal movement wouldn't clip corners would it? actually, no. no matter the size of the tiles, moving diagonally from the center of one to the next with a non-zero radius swept area will always intersect the (potentially impassable) tiles to the left and right along the path. the "padding" must be added at a higher resolution - a smaller tile size.
what about a tile size smaller than an entity's diameter? for collision maps, you just check a bbox of tiles the size of the critter, instead of a single tile. i guess you'd do the same for astar maps?
that would let me use just one set of maps at 1 foot per tile for all critters, instead of maps at various critter diameters per tile.
EDIT: i double checked the code. astar is using a map with tile size = entity diameter. and it does do diagonal. and it does not "grow" the obstacles by the radius of the entity. so it looks like clipping corners is the issue.
suggestions?
grow obstacles? clearance based? no diagonal? no diagonal with path smoothing?
took a look at the clearance based article, clearance values and HAA map may not be suitable for real-time on the fly on-demand generation? it looks a bit intense...
tried doubling the scale of the astar map vs the collision map. didn't seem to work. but i probably didn't scale up then back down correctly.
i'm thinking a single astar and collision map with a tile size of 1, and check a bbox rad=criiter rad of tiles around a tile for both astar obstacles and collision checks. this would mean just one map, and would effectively "grow" obstacles for use with diagonal astar movement. so a tile would only be traverse-able in astar if all the tiles in a given bbox rad around it were traverse-able. this would work, wouldn't it? i would think it would be fast enough too.
Need a system that first allows FAST (least processing) culling of the situation which doesnt give False-Netatives
Probably including some space dividing system to limit the set of candidate obstacles from the earliest
THEN detailed collision checking is done upon the remaining rough Positive indicators to determine True positive/negatives,
at which time the (more) exact/precise collision detail also would be used to create the appropriate reaction to movement
(stopping/deflecting/sliding)
You may need to use both a point obstacle system (useful for dynamicly moving obstacles) and for continuous surfaces (frequently an area mesh)
so are there any other options available besides: 1. clearance based 2. enlarging obstacles on the astar map 3. no diagonal movement
Personally I would ditch the grid and partition the space up in a more efficient way, but it's your choice. The A* algorithm has nothing intrinsically to do with grids and they're usually a poor choice unless you already have that grid for some other purpose.
If you want to treat 2 squares as adjacent even though the route between them is diagonally and thus infinitely narrow, you need a special-case workaround - simply checking the 2 squares either side of the diagonal for passibility should be sufficient. As an example, looking at a keyboard's numeric keypad, you can't move from 5 to 9 unless both 8 and 6 are clear too. 9 shouldn't be generated as a successor node to 5 if 6 and 8 are not both clear.
This might be of interest to you: http://www.gamedev.net/topic/575717-pathing-with-variable-unit-radius/
Back then I didn't know about clearance based path-finding, but that's basically what I was doing. Generating the path info was a step that happened in the editor and took quite a bit of time because of the many intersection tests I was performing in determining if two graph nodes were connected, not really suited for real-time procedural map generation (though I was much worse at writing performant code back then). Is this something you have to do for your generated maps? Or do you have that info preprocessed for 'chunks' or something similar? You might be able to preprocess clearance values as well. E.g. if you have a rock 'chunk' that takes up 2x2 tiles, you could store the clearance values of the surrounding 12 tiles for that rock.
Is this something you have to do for your generated maps?
no. there's no real pre-processing. the world map determines the terrain in the area. large tiled sparse matrix pattern maps determine the location of obstacles like rocks and trees. from this info a terrain chunk (including ground mesh), an astar map and a collision map are generated in realtime on the fly as needed, with caching.
its all driven by two routines: get_chunk_index, and get_collision_map_index. they both take a location. get_collsion_map_index also takes a critter radius, which determines the scale of the map (the size of a tile). these routines handle the caching and realtime generation of the chunks and maps. astar is run on a collision map to determine path. while moving along the path, a collision map is used to check for collisions - it can be the same one as used for astar or a different one at a different scale.
the world map is 500x500 tiles, tiles are 5 miles across. pattern maps for trees and rocks are 800x800 feet in size. terrain chunks, and collision and astar maps are 300x300 feet in size. astar stops when path length reaches 50 feet or so. only the first two nodes of the path are ever used.
Hmm, I think post processing the path and smoothing it out might work, though your still not guaranteed to miss corners. Have you thought about letting steering do the work of getting around corners & making the paths look a bit more organic? You'd probably need it anyway to avoid collisions with dynamic obstacles (ie the player or other creatures)
You could also try a 'thick' line test to ensure that traveling from one tile to another doesn't have the agent crossing through a blocked tile and then consider that passage blocked.
