SFML community forums

Help => General => Topic started by: GroundZero on August 27, 2012, 05:02:11 pm

Title: Pathfinding A* tutorial, help me out please
Post by: GroundZero on August 27, 2012, 05:02:11 pm

Good evening everyone,

After 4 days of trying I still am struggling with implementing a pathfinding to my game.
I want to learn how to completely from scratch write my own, instead of using Boost or anything.

I was hoping that someone with experience can show some examples and -or explain some stuff
to me if possible. It would be highly appreciated.

My questions:

1. How should I build up my map?
I have a 800x800 map (pixels of course lol). I would like to cut it in nodes of 40x40 pixels.
I am using sprites (at this moment only RectangleShapes, but will be sprites) which I will be placing on my map (PNG images).

I store all my sprites in a vector, so that the sprites (textures) will exists as long as the program is running. If I wouldnt do that, the program would crash and -or result in an error.

So what I have is:
- 800 x 800 SFML Window
- Class that draws the sprites in the window (lets say 2 walls in this example) named level1.h
- Vector (level1.h) which holds all the sprites that I need to draw in the level
- Class that draws the player sprite in the window  named player.h

Is this the correct way? or should I store stuff differently when making use of A* pathfinding?

2. How do I add the grid?
is this just screenWidth / 40 (pixels) + screenHeight / 40 (pixels) = amount and then draw RectangleShape's all over the window, so I have a visual grid (which wont be displayed in the final version of course)? so basicly its just a grid for our reference so we can see what and where during the development, and to get pixels (width and height) for our codes.

3. Now I have the grid, how should I add the path? i.e. where sprites may or may not walk. Where my spirites are drawn on the map, no walking is allowed. If no sprite is there, then walking should be allowed.

- Should I just make a vector with all the nodes in it (x-pos and y-pos) which are allowed to walk on?

4. Now we know where we are allowed to walk, how and what code should I implement? I am struggeling to think of / write the right alchoritm.

I know it has to be something like the following illustration (sorry for my poor drawing skills lol) but I have no clue on how to code this into a while loop or what so ever.

(http://img109.imageshack.us/img109/7102/sampleq.png)

5. How to move the sprite to the target following the best way possible which was calculated in the A* alchoritm.

Well, I hope someone can help me to get on the right track.

Best regards



P.S. Some info on my sample picture so you know what I meant:
Green square = player
Red square = a enemie which will walk towards you (I know it says finish lol)
Blue is a wall, which cannot be walked over and -or through

Yellow line is the most efficiënt line. Because you go diagonal each movement would cost 7 points (for example). In total the costs for getting to the finish would be: 35

The orange line is an alternative line (just as example), the total costs would be: 120 points.

This because going horizontal or vertical costs 10 points.

EDIT:
I found a good sample picture of what I meant:

(http://adamatomic.com/pics/blog/a_star/maze11.gif)

Title: Re: Pathfinding A* tutorial, help me out please
Post by: kaB00M on August 27, 2012, 05:27:50 pm

http://www.policyalmanac.org/games/aStarTutorial.htm (http://www.policyalmanac.org/games/aStarTutorial.htm)

This helped me a lot.

You need a consistent collision system.
Also, a way to move your sprites/characters in a designated path you choose.

Without this two, you wont be able to do it.

Title: Re: Pathfinding A* tutorial, help me out please
Post by: GroundZero on August 27, 2012, 06:11:52 pm

hi kaB00M thanks for your answer.
The idea I have is that I can just freely walk around with my sprite (the one controlled by the player).
The only thing that will prefent from hitting walls or w/e will be the collision detection.

I got that part, but the part I need now is the part which will move the (in my instance) zombies towards the player.

i.e. I spawn 3 zombies at different locations:

1. 750 x 600 pixels
2. 320 x 432 pixels
3. 532 x 252 pixels

Now they should start moving towards me, but they should use the path that is available, and calculate the shortest route possible to get to the player.

I do NOT want to make the player walk towards a point after a single mouse click (like most classic RPG games). I am controlling the player sprite with the arrow and W, A, S, D buttons on the keyboard. So it's like the idea behind most 1st person shooters.

Walk with the keyboard, aim with the mouse :)

Title: Re: Pathfinding A* tutorial, help me out please
Post by: kaB00M on August 28, 2012, 08:45:32 am

The way I did it was to divide the map in tiles. So every character has a 'real_x' and a 'tile_x', and a 'real_y' and a 'tile_y'.

So instead of  'one zombie is at location 750 x 600 pixels' (real position), you should say 'one zombie is at location 18, 15', since your tiles are 40x40.

Collision should be checked this way too. 'Is tile 8, 8 passable?,' for example.

In a Cartesian coordinate system, you will be using quadrant IV. Just like Sfml's position system.

The way the algorithm works is that it calculates the path and puts it on a lists. It does not calculate the path each frame!

So lets say the zombie wants to move from 0, 0 to 3, 0, and there are no collisions between them. The zombie has to walk right to 1, 0  then 2, 0 then 3, 0.

You have to make FIRST a system where you can assign a zombie a PRE-DESIGNED path YOU give. We can also called it a  'canned path'.

First make this system and give the zombies different paths. Make the zombies walk in circles, for example.

0, 0 ->  1, 0 ->  //moving right
1, 1 ->   //moving down
0, 1 -> //moving left
0, 0 //moving up
 

What the A* algorithm does is give you the DATA you will put inside this system. So you have to make this system first.

Title: Re: Pathfinding A* tutorial, help me out please
Post by: GroundZero on August 28, 2012, 11:17:37 am

Thanks for your replies guys, ill give it a try :)