Jump to content
  • Advertisement
Sign in to follow this  
Norman Barrows

collision and astar maps, variable entity radius

This topic is 650 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

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)

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
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.

Edited by Norman Barrows

Share this post


Link to post
Share on other sites

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.  

Edited by ferrous

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!