Sign in to follow this  

Tactics moveable area

This topic is 4284 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

For a tactics rpg how would I go about effectively finding the all the possible movements for a sprite if movement isn’t locked to a tile, I tried just making a grid and using a A* but it cant work its way through narrow passages if its not correctly aligned

Share this post


Link to post
Share on other sites
If I understand your question correctly, you're asking how to perform pathfinding on a continuous surface (rather than a disrectised map). Is that correct? If so, the answer is to perform your search in the action space of the object, rather than its state space, where the action space is defined by the set of commands you can give to the object; e.g., steering angle, speed, acceleration, etc.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
We learned about this sort of algorithms in robotics class,
obstacles are 2d polygons, sprite (robot) is a 2d disc.


The problem is more complex if the sprite shape isnt circular (since you need to take orientation into acount) and we hardly touched it in class.

The algorithm is based on the (usualy valid) idea that going in a straight line is best (when possible). When an obstacle is in the way the sprite should head to go along its "corners" almost touching the obstacle.


If the sprite shape is circular the algorithm was:

1) You transform the physical obstacles world into another representation where the sprite is a dot. To do this you simply enlarge all the obstacles by the the sprite radius (all around them). This way narrow passages that the sprite can't go through will not be any passage in the transformed obstacle domain (you need some union algorithm to change touching polygons into one polygon).

some ascii art to explain


______ O <--- sprite
|_____| <--- obstacle
.----. <--- too narrow passage
| | <--- 2nd obstacle
transforms into

/------\ . <--- sprite (turned into a dot)
| |___ <--- obstacle (enlarge all around by radius)
\--. \ <-- narrow passage is now gone
| |




2) the next step in the algorithm is to build a graph from the new obstacles vertices. The graph is built so that an edge between two vertices is made if there is a line of sight between them. There are some vertices that you dont need to take into account (I dont currently remember the criteria which are needed, something with the tangents to the obstacle). You add two special nodes - the start (where the sprite is) and the target (where you want the sprite to move). You put an edge where there is line of sight between two nodes.

3) then you can do A* on the graph (heuristic - euclidian distance).

notes:
- you can build most of the graph in advance (if the obstacles are not changing) and only add the start and target nodes.
- my memory on this is very rusty, you better find a more qualified source before you try to implement it. I'm sure 3d games have solutions for such problems.

good luck!
Iftah.

[Edited by - Iftah on March 26, 2006 6:21:59 PM]

Share this post


Link to post
Share on other sites
@Iftah
Il think about applying your solution but hopefully I can figure out something simpler, since its for a turn based system it doesn’t need to be precise and there no danger of getting stuck on a corner since collision detection will be disabled when the sprite actually moves, so basically it doesn’t have to work perfectly, just look believable.

Share this post


Link to post
Share on other sites
what about making the obstacles in a very small grid?
if the map isnt big even pixel by pixel grid can work.

another possibility is the make a regular 32x32 grid and on squares where obstacles are you can make the grid finer say, 2x2 squares. This means you can't use simple 2d array but a more complex data structure but the A* algorithm will work just fine with it.

Share this post


Link to post
Share on other sites

This topic is 4284 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this