Hello, I'm new here... my first project and my questions

[Finn]

Well if you're still looking for trace-routing....
this is how I made the enemys follow my character:

Check the distance between the character and the enemy,
if character is in enemy's aggro-range, then

(pseudocode)

Code: [Select]


if(X_Enemy > X_Player)
    Enemy.Move(-Speed,0);
else
    Enemy.Move(Speed,0);

if(Y_Enemy > Y_Player)
    Enemy.Move(0,-Speed);
else
    Enemy.Move(0,Speed);


and then just check collisions and you're done. If you want to walk around it's something like the code above. Just a few changes

[GreenFlame]

SFML 2!?
I thought 1.6 is the latest, and i'm using 1.5 currently.

Also why did you change if to while?

An about this freezing:
I guess that if you put one of objects inside another one the program tries to move them from collision positions and goes into infinite loops, should be it is because of my collision detection idea, if one object never was inside another one he won't get there because collision won't allow.
There are some ways to solve that bug, but i'm not sure if such or similar method of object palcing will be used, so i leave it for now =)

[GreenFlame]

If you mean this algorithm:

Code: [Select]


if(X_Enemy > X_Player)
    Enemy.Move(-Speed,0);
else
   if(X_Enemy < X_Player)
    Enemy.Move(Speed,0);

if(Y_Enemy > Y_Player)
    Enemy.Move(0,-Speed);
else
    if(Y_Enemy < Y_Player)
    Enemy.Move(0,Speed);

then movement will be not so natural: Enemy will move in diagonal way and when objects' X or Y are equal it will move straight.


I think it would be better to use something like:

Code: [Select]


if(needToMoveCloser)
{
  angle=getAngle(Enemy, Player);

  Enemy.move(speed*time*cos(angle), speed*time*sin(angle));
}

Then Enemy will directly follow Player.


But still, it doesn't allow to avoid obstacles... also, do you use Perfect Pixel Collision in your RPG? Doesn't it eat too much framerate?

And thanks for support, everyone =D

[Finn]

Yes I'm using the Pixelperfect test...and actually: No it doesn't eat too much
Well...At the moment I'm just testing 4 objects for collision but I'll see later if it's possible with 15 and more objects!

But I have mapscrolling...so if the test eats too much I'll just add something to only test the objects you can see at the moment.

To tracerouting:
I don't change the angle, because I have different animations that fit for each direction.
And just add this line to ensure, the enemy stops if he catched the player:

Code: [Select]


if(Player_X == Enemy_X && PlayerY == Enemy_Y)
   return;


For avoiding objects just do something like:
Save the direction the sprite is moving,
Check if the enemy is colliding with any object.
(for exaple the sprite is colliding with an object and moved right-->)
Check if the player is higher or lower then the enemy. If the player is above move up, then right. If colliding move up again and then right. As long as you're not colliding anymore. Then you can go on normal movement


Hope you understand what I mean
[/code]

[Nexus]

The best (and really, only) algorithm for pathfinding is called A* (A star). It's pretty simple to explain, but not trivial to implement.

That's why you don't implement it yourself: Boost.Graph. I would prefer Boost over your current implementation because the library is highly portable, known to a big part of C++ developers and quality-checked as well as optimized over time.

By the way, A* is neither the only nor the best algorithm for pathfinding. The choice depends on the exact problem.

[Xorlium]

What do you mean it's not the best?

Among the problems that follow the standard "informed graph search" algorithm, meaning they do this:
 -Maintain a data structure of paths called "frontier"
 -Start with the start node and each iteration pick some path in the frontier,
-Check if it's a goal, if not, replace it by the neighbors.

The other algorithms only differ then in which node to pick to expand.

Among them, given a Heuristic, A* is indeed the best. it is proven to be optimal and optimally efficient, which means that, among the optimal algorithms, this is the one that expands the fewest nodes (except for how to break 'ties' when two paths cost+heuristic are equal).

[Finn]

But does it work that good with non-tile-based games, too?

[Xorlium]

Hmm... yes, it does, and it works very well I might add. You just have to choose where the nodes are located.

You can do this in many different ways. For example, you might choose a grid graph, or a hexagonal-grid graph (I suggest the latter)

Boost.Graph is a good idea, but I wanted to do my own, and I wanted to modify a lot of things.

Sure, mine is not extendable or anything, and it only works in my game, but oh well.

[Finn]

Well. I think this sounds way too complicated! I think I'll try my own solution. If it works I'll keep it, otherwise I'll try the A* algorithm.

[GreenFlame]

To Finn
So, your algorithm is:

For avoiding objects just do something like:
Save the direction the sprite is moving,
Check if the enemy is colliding with any object.
(for example the sprite is colliding with an object and moved right-->)
Check if the player is higher or lower then the enemy. If the player is above move up, then right. If colliding move up again and then right. As long as you're not colliding anymore. Then you can go on normal movement

and it'll work in this case(E - Enemy, P - Player, O - Obstacle):

Code: [Select]


       P

   O
  EO  
   O
   O


but what to choose if E.Y == P.Y, how to choose what's better(faster) - to move up or down?

Code: [Select]



   O
  EO  P
   O
   O




or what to do if Enemy is surrounded? He can't move right, so he tries up or down, but if the are blocked?

Code: [Select]




  OO
  EO  P
  OO



I can suggest something like this for Enemy movement:

Code: [Select]



R) If right is not blocked
move right

A) If right is blocked
 move up(down) (choose randomly or depending on Player's position)
 then make check and select R or B

B) If chosen up(down) blocked
 try down(up)
 then make check and select R or C

C) If both up and down are blocked
 move left and move up(down)
 then make check and select R or B

Repeat it until we can use R


So it is only for "move right" check, there should be made 3 more check for the other 3 directions, i'm not so sure, but i think this code is ok for such kind of "trap"(and its variations):

Code: [Select]



   OOO
     O
     OOO
      EO  P
      OO
      O
     OO



But still it doesn't look so natural( that's why i'm going to read about A*), the Enemy would look not so smart, he should avoid this "trap", without this "research".

Should be it is hard to understand what i'm trying to say about my algorithm,but if you try to track Enemy's path yourself in your mind it could help.


To Xorlium
You said A* is good... I checked Boost.Graph link, there is enough code...so, i think first i'll read about A* in my book and try to understand if it is really good for kind of game i'm developing.

So, you tested my program(special thanks), could you tell me:
1)will A* work if different object have different sizes?
2)will the be be able to avoid each other and obstacles?
3)how many objects' pathfinding is optimal for A*?
Sorry for that many questions again =)

Thanks for the help and good luck, everyone =D

[Finn]

Just a quick thing:
I tested the pixelperfecttest now. If I use it without limiting the framerate I get more than 400 fps. Though I limit the framerate to 60. So this shouldnt be a problem! At more than 400 fps there is enough space for much more objects to do the pixelperfecttest

[GreenFlame]

That's cool thing!, may be i shall retest my algorithm with Perfect Pixel test or change it a little =)

[Xorlium]

Hello.

Yes, if it's a simple game with not many obstacles, A* might be overkill. A* always returns the 'best' path.

And it does work for units of different sizes, you just need to calculate intersections and see if a node is valid based on a parameter (the size).

So when adding new nodes to the "frontier", check if transversing the edge would make the unit collide with an obstacle, and if so, don't add that node.

I haven't used Boost.Graph, so I'm not sure if one can modify all that (but probably... I imagine one gets to choose the 'neighbours'). That's part of the reason I made my own, so that I could modify the options and anything I wanted. Also, Boost, while very useful, doesn't concern itself with ease of use...

[Finn]

@Greenflame

Yeah, you're right! My Algorithm was uncomplete. But your solution isn't that much different...you just finished my thought
But anyway you're right

[GreenFlame]

Tested my collision algorithm and perfect pixel test(both with 17 objects, each is made of 2 sprites) in 2 modes:

A test: only 1 object moves and collides in every possible way(constantly)
B test: 1 object moves and collides in every possible way(constantly), other ones are just rotating and several colliding a little

My collision algorithm
A test: 650 FPS
B test: 350 FPS

Perfect pixel test
A test: 320 FPS
B test:  90 FPS

So, pixel perfect collision test is more expensive, but it is very sharp!
But I'm not sure if it is good framerate(in perfect pixel test). The framerate should be faster on such games as i'm developing(tested with GeForce 9600 GT,  a little more than 3 GB RAM,  core 2 Quad 2,5 HHz processor, 1024*768 windowed) what could you say?