SFML community forums
General => SFML projects => Topic started by: GreenFlame on September 05, 2010, 03:25:51 pm
-
Hello everyone, my first post here! =D
Some intro:
I'm a beginner in game development, I wanted to create games since my childhood but i had no idea how to do that...(i think you are familiar with this kind of story).
So, in school i had some programming practice in Visual Basic at lessons and i finished an additional 2 week programming course(which repeated school material) before my graduating exam. I graduated from the school and now I'm a student.
I have been enjoying write programs since i've understood how to do that =)
I decided to learn C++ to make my dream become reality, so with time i came here.
Sorry for my English and
Good Luck, everyone! =D
-
Here is an exe of my first serious project, obviously using SFML
the link(748.69 kB)
http://www.megaupload.com/?d=SVXK2A31
If i may compare, the gameplay is going to be similar with Battlefield game series(usage of classes, vehicles, also some special abilities etc.)
I know it has bugs and doesn't look like game yet, so i need some help:
1)First, i'd like to ask about pathfinding, what algorithm is the best for such type of game?
2)Second, i'd like to ask about collisions, i've made my own rectangle-to-rectangle collision detection, but i'd like to have something more advanced, i've heared about Box2D and Cmake, could anyone tell me a little more about them?
Thanks in Advance =)
-
We have a nice class in the wiki for collision-detection! Just take a look at it :)
What do u mean about pathfinding? For example enemys following your sprite?
-
If you mean this
http://www.sfml-dev.org/wiki/en/sources/simple_collision_detection
then i already know it, i tried it and rectangular collision looked bad for me, pixel perfect test is perfect but takes too much resources, may be i used bad algorithm... but it works very fast with my own rectangular collision.
So, when i tested collision form the link it approximately looked like this:
if(window.GetInput().IsKeyDown(sf::Key::Up) &&
!window.GetInput().IsKeyDown(sf::Key::Down))
{
sample.sprite.move(frameTime*speed);
if(Collision::PixelPerfectTest(sample.sprite, sample2.sprite, 127))
{
while(Collision::PixelPerfectTest(sample.sprite,sample2.sprite,127))
{
sample.sprite.move(-1*frameTime*speed);
}
}
}
Also i've just realized that i can jsut remove the while loop)
And about pathfinding. Yeah, for example following, or moving from point A to point B, it is simple if there is only moving object, but what to do if, for example, there are some obstacles or other moving objects?
And thanks for reply =)
-
The best (and really, only) algorithm for pathfinding is called A* (A star). It's pretty simple to explain, but not trivial to implement.
I wouldn't pretend to explain better than wikipedia: http://en.wikipedia.org/wiki/A*_search_algorithm
-
I got some material about the A* a few days ago when started to search for algorithms, started to read, but looks like it is good only for tile based environments... or no? :roll:
So will it work with continuous environment(i use such type in my project) or is it worth to make my project tile-based?
Is it good for real time game?
Is it good for kind of project i'm working on?
You can run the project if it'll help to answer, here is the link from the 2nd post:
http://www.megaupload.com/?d=SVXK2A31
Thanks in Advance =D
-
Hello,
Yes, it's very good for non-tile-based environments. The thing is to construct he graph "on the fly", not have it constructed beforehand (since it might be way too large to store), and that's one of the advantages of A*: it doesn't need to look at the whole graph or keep it in memory, just a function that for each node, it returns a list of neighbors.
I'm using it in my own game, and it works beautifully (and quickly!) and I'm not using tiles.
I recommend that you add a visual element while you program it. For example, render a little white dot for every node expanded, that way you can see exactly what it's doing.
BTW, the link doesn't work, it says it's deactivated.
-
Construct on the fly...hmm I'll read an article from my book about A* and then re-read your message =)
Thank you very much for reply, you gave me some inspiration! =)
Quite stragne, i uploaded the file 3 times but still it gives the same link...
http://www.megaupload.com/?d=SVXK2A31
Here is a rapidshare link, but looks like server is overloaded atm
http://rapidshare.com/files/417254555/The_First_Real_Project_v_0.0.6.rar
So, what's better for file hosting? =)
-
Hmm, I downloaded it, but it's for windows only...
-
Oh, yes, it's for windows, i'm sorry... btw how can i set my MVC 2008 to make Linux builds?
And what link worked for you?
Sorry for an avalanche of questions and thank you! =D
-
Oh, yes, it's for windows, i'm sorry... btw how can i set my MVC 2008 to make Linux builds?
And what link worked for you?
Sorry for an avalanche of questions and thank you! =D
Edit: accidentaly double posted, sorry, can i delete the post?
there was a checkbox with delete option...or no?
-
Heh, well, I don't know anything about cross-compiling, but I don't think it's easy at all. The link that worked was the last one you posted on megaupload.
If you post the source code I can compile it myself.
-
Here is the source code, i hope i sent all the required files:
http://www.megaupload.com/?d=R2DK88SO
Any comments on code are welcome =)
And it looks like megaupload works only time to time, so... any suggestions on what to use for file sharing?
-
Here is the source code, i hope i sent all the required files:
http://www.megaupload.com/?d=R2DK88SO
Any comments on code are welcome =)
And it looks like megaupload works only time to time, so... any suggestions on what to use for file sharing?
64digits.com
-
Hello,
I took a look. I'm using sfml 2 instead of 1.6, so I had to change a few things (easy things) to make it work, such as the names of some functions and so on, but now there are a few bugs.
Change:
if (window.GetEvent(evnt))
to
while(window.GetEvent(evnt))
And aslo, if I click with the mouse button many times on the screen to make many... mm... tanks? well, it freezes.
-
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)
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
-
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 =)
-
If you mean this algorithm:
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:
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
-
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:
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 :P
[/code]
-
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 (http://www.boost.org/doc/libs/1_44_0/libs/graph/doc/astar_search.html). 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.
-
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).
-
But does it work that good with non-tile-based games, too?
-
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.
-
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.
-
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):
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?
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?
OO
EO P
OO
I can suggest something like this for Enemy movement:
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):
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
-
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 ;)
-
That's cool thing!, may be i shall retest my algorithm with Perfect Pixel test or change it a little =)
-
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...
-
@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 :)
-
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?
-
To Finn
Yeah, it isn't different, just more complete, but still, this kind of movement isn't that natural... So, i hope A* looks more realistic... I've spent my free time today on Perfect Pixel Test comparing =)
Also, could you give me an exe or source code for your project, i'd like to test it on my configuration and see what is framerate in your game with Perfect Pixel Test(You can see framerate in some tests for the project i'm developing at the end of page 2). Please, post it here, or PM me, or just do not do that if your game isn't open-source.
And Good Luck =D