A* pathfinding work with big open list

Question

I work on a project which demands to use A* algorithm. In this project you select your player with the left click and you guide him in the map with the right click, like the gameplay of thousand strategy game. The graphics are 2D, a little like the game Don't Starve and the game is developped with SFML / C++.

I need to use A* for the deplacement of the player, indeed if an obstacle appears on his road he has to avoid it. But for the moment, i don't know how to apply a grid to the map, i want to place any tree / rocks and other stuff anywhere in order not to see the grid cells. For now the open list is only composed of pixels, which is not the good solution I think ^^, the algorithm is pretty slow. If you have any solution for a realistic rendering while keeping a fast algorithm I'd be happy to hear it. :)

Thank you in advance,

Answer 1

Do you have a screenshot?

The pathfinding grid, and rendering grid can be different. Zelda used different sized tiles for movement and rendering.

navigation mesh

This may be overkill for your map structure, but you may use a navigation mesh.

,

edit: If you haven't read it, Amit has a great resource: http://theory.stanford.edu/~amitp/GameProgramming/

Answer 2

What you're looking for is discretization. Behind this obscene name stands a simple principle : you can't deal with an infinite amount of data.

You need then to perform a transformation on your world : instead of allowing your character/unit to go at any location (x and y being real numbers), you can divide your world into some sort of a grid (this is what the navigation mesh and waypoints are doing), and only allow your char to go on these cells (or points, you can see it as you want). This is discretising : you are going from continuous values (real coordinates) to discrete values (integer coordinates / point). The more precise you go, the nicer it'll look.

After doing this, assigning moving costs between cells/points is rather simple, and performing A* on it as well.