Hello, I need to calculate the shortest path between two points with the ability to circumvent obstacles.
Description tasks:
PLAYING field is a 10x10 matrix (a unit of measurement - Cell)
The player is in a 5x5 cell. It needs to be moved to a cell 8x9, but in different locations facing objects that are preventing it from doing so directly. There must be an algorithm that helps to calculate the path of bypass obstacles.
crioto 0 Newbie Poster
MattEvans 473 Veteran Poster Team Colleague Featured Poster
Look for any information you can find about the A-star graph-search algorithm. It's a heuristic-based best-first search -- it is pretty much the de-facto 2D pathfinding algorithm, and it works well in tile-based maps. This is probably the best introduction to A-star, specifically for tile maps: http://www.policyalmanac.org/games/aStarTutorial.htm
Alternatively, if that seems a little over-the-top ( it can eat memory like you wouldn't belive in big, fine grids with lots of good-looking paths at the begining [ i.e. mazes ] ), consider using http://en.wikipedia.org/wiki/Dijkstra's_algorithm to find all the best paths when the 'game' starts, and store them in a matrix that shows the best path from every cell to every other cell.. that's very fast in-game, but can also result in a massive, permanent structure for the duration of the game. If your obstacles are all 'simple', and they move about, like lots of small rocks or other agents in the way, consider using a steering approach rather than pathfinding; steering is cheap at runtime and free at initialization time, so, use that if and anywhere that you can.
A simple steering approach is always turn left ( or right ): basically; plot a curve ( a series of line segments ) from the start to the end point; every time the line segment intersects an obstacle, add a new line segment to the curve that goes 'left' as close as you can to the obstacle, once the obstacle is 'cleared' add a line segment that goes back to the end point, and keep checking the last added segment. You can do this in real time - keep moving 'forwards', if you bump into a wall, turn left, and always gradually try to turn back towards the goal point. It can result in the agent getting 'stuck', of course: i.e. if the agent can't ever reach the goal point, or is stuck in a complex configuration of obstacles. Also, picking either 'left' or 'right' as a blanket rule results in biased behaviour that sometimes looks stupid ( i.e. missing a tiny route on the right to take a huge route that hugs a long curvy wall on the left ), and randomizing left and/or right results in erratic behaviour. I'm using steering like this in places at the moment; but the turn direction is based on weighted calculations of the spacial density on the agent's left and right side respectively - it works, but still has issues.
crioto 0 Newbie Poster
The proposed steering you approach - is not very suitable for my purposes. That's because it often in my scene can be a situation where towards the end point will be too many objects. Perhaps, as you say - it will look silly. Thanks for the links
If I solve this problem - wait my tutorial
Phaelax 52 Practically a Posting Shark
a-star will work, it doesn't matter how many obstacles are in the way. If there's a path available, a-star will find it.
MattEvans 473 Veteran Poster Team Colleague Featured Poster
The thing I dislike about A-star is that, when it can't find a path, it degrades to searching the entire space, with a massive memory overhead to boot.. If you're using A-star in a real tile map or graph, where each tile/graphnode is actually represented by some set of properties, consider dropping the 'closed set' / 'open set' idea, and marking each tile as you pass through it ( i.e. by setting a flag in the tile's properties ). It's very much not thread safe to do that, though.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.