1

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,

thegrandwaazoo
  • 301
  • 2
  • 15

2 Answers2

2

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.

enter image description here , enter image description here

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

Community
  • 1
  • 1
ninMonkey
  • 7,211
  • 8
  • 37
  • 66
  • I was initially a little confused by the Zelda comment, because A Link to the Past doesn't perform any pathfinding. – Collin Dauphinee Sep 24 '13 at 22:15
  • I can't make screenshot for the moment :/, i had a question about the navigation mesh, how i'm suppose generate all these polygons ? And make a link between waypoints and navigation mesh ? – thegrandwaazoo Sep 24 '13 at 22:33
0

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.

teh internets is made of catz
  • 1,450
  • 2
  • 13
  • 25
  • I don't see exactly how it suppose to work. I put my obstacles on the map and i need to connect them with polygons, but the creation of the grid with discretization looks pretty random, could you clarify this for me ? – thegrandwaazoo Sep 25 '13 at 20:35
  • If your obstacles are positionned onto some cells of the grid, you knows these cells aren't walkable. Are they complicated shapes or just some squares/rectangles ? – teh internets is made of catz Sep 25 '13 at 22:11
  • They are just rectangles for the moment, so if I see what you're telling me, I put my obstacles in the map and after I divide my map with discretization. However I don't see exactly how to take into account the position and size of the obstacles with the division of the map.... – thegrandwaazoo Sep 25 '13 at 22:31
  • Simple (maybe dumb, you'll have to see that yourself) way : you have placed you rectangle at the point p1(px;py). You know after discretization that the cell containing this point is c1, by doing an integer division on your points coordinates (dividing them by the width and height of one cell), so that it's for example c1(3;4). You can repeat this operation on the 4 points of your rectangle, so that all the cells between c1 and c2, and between c1 and c3 are occupied by your rectangle. Telle me if it isn't clear, I'll make a simple schema and edit my answer when I find some time (maybe tonight) – teh internets is made of catz Sep 26 '13 at 08:34