Messages

1

General / Re: [Threading] findPath

« on: January 03, 2013, 01:39:06 pm »

It's still more efficient than a container that implicitly sorts every time it is modified. If you use std::set, you don't notice but the library iterates many more times over the data structure than you might need. If you use std::vector, yes you have to iterate over it too, but because you yourself do it, you are sure it isn't done more times than necessary.

I've updated my code and the speed has indeed increased! the game is now much more playable, still a little lag, but it's okay, I think I've done as much improving as I can.
Thanks for your help!!

2

General / Re: [Threading] findPath

« on: January 03, 2013, 12:09:17 am »

OK, here are a few things you might want to look at:

• If you take my advice and use std::vector or std::deque, don't insert and erase so much. It is expensive no matter what data structure you use. Rather try to use boolean values to mark nodes as done or not.

I see what you mean, but I just adjusted the algorithm and I'm kind of stuck now.
In my while-loop, I don't erase the least weighted element now, instead mark it as "scanned". But now I have to make sure I select the non-scanned least weighted element of the vector. But I'm not sure if looping through the vector to check is efficient.[/list]

3

General / Re: [Threading] findPath

« on: January 02, 2013, 10:17:14 pm »

OK, here are a few things you might want to look at:

• Use (const) references more. They help avoid unnecessary copies since you only read many of your data structures.
• Avoid making temporary objects if you intend to just pass them to some function and let them go out of scope. If you are using a C++11 compatible compiler, just construct the object within the argument list and it will invoke the Rvalue reference variant of said function.
• Move your integrity checking outside of your main loop. Doing it every iteration can become quite expensive.
• If you don't intend to make use of the exceptions that .at() can throw use operator[] instead. This saves time since you make sure that you will never access any element out of bounds anyway.
• Try to use "more efficient" data structures. Instead of using the implicit ordering of a std::set, you can try to use std::vector or std::deque and sort it yourself when needed. This saves a lot of time when inserting and deleting.
• If you take my advice and use std::vector or std::deque, don't insert and erase so much. It is expensive no matter what data structure you use. Rather try to use boolean values to mark nodes as done or not.
• Try to avoid using iterators where possible. Traversing a container with an iterator is more expensive than using direct array indexing if you don't intend to modify the container.
• You might want to experiment with using the A* algorithm instead of plain old Dijkstra's. With a decent heuristic it can be much faster in most cases.

I estimate that the majority of the time that your path finding algorithm is running, the CPU is actually busy with allocating and freeing memory. In any performance critical case such as this it is really worth-while to open up your profiler tool and gather performance data, it will help you optimize out the hotspots if you didn't already do it from static code analysis.

Awsome tips, I started working on my project again, starting with the Dijkstra with these things in mind. Also, we have to use Dijkstra :c, so I'm not allowed to implement A* algorithm.

Thanks for the tips!
And thanks to everyone for replying, I'll post the result!

4

General / Re: [Threading] findPath

« on: December 24, 2012, 02:32:16 pm »

I'll PM it , I'm sorry I can't post it in public, I'm a bit paranoid when it comes to school checking for fraud (and publishing my code could make them think I copied it from this thread)

5

General / Re: [Threading] findPath

« on: December 23, 2012, 05:21:21 pm »

The problem is, right now, I made the algorithm as fast as I could, I call it every 2 seconds, it checks the path for each node, with the player in mind, so every node knows its following node, until they reach the player. So I don't have to re run the algorithm for every NPC I have, but still every 2 seconds, I have this major lagspike

6

General / Re: [Threading] findPath

« on: December 20, 2012, 10:46:03 pm »

Parallel programming isn't a trivial topic at all and if you want to dive into it, it's advised to get some good literature on the topic and/or at least understand the basic concepts of threads and mutexes and understand what race conditions and deadlocks are and how one can resolve them.

But for your problem, it'd say you shouldn't try to fight the symptoms (not enough CPU cycles) but fight the actual problem (slow/bad algorithm). Granted I don't know your algorithm but I doubt there's no way to optimize it and even if so, you might want to think about an different algorithm which is made for games.

Yes, the truth is, this is for a school project and I have no idea on how to optimize the code, I create 3 maps, with coordinates of the nodes as keys, the algorithm, indeed, is pretty messy, but I was hoping to cover that up, simply because I don't have time to find ways to improve the algorithm

7

General / Re: [Threading] findPath

« on: December 20, 2012, 10:43:49 pm »

http://www.sfml-dev.org/tutorials/2.0/system-thread.php

Peruse the "Protecting Shared Data" section.

The main problem is that your mutex is defined in the Thread::Run definition instead of being used there.

Thank you for your reply!

Sorry, this is my first time I write a multithreaded program, do I allocate a new mutex and then pass a pointer to the mutex to the thread for the thread to use, and use also use the same mutex when reading from the array in NPC::walkPath()?

8

General / [Threading] findPath

« on: December 20, 2012, 08:37:54 pm »

Hello,

Currently I have a pathfind algorithm for a set of enemies, which uses quite alot of resources and CPU time. So before I ran the algorithm each frame, causing alot of FPS lag. So I made a class with a thread, that takes care of the calculation.
So here's a sketch of what I have:
Npc class

class NPC {
public:
      void setPath(std::vector<Node*>);
      void walkPath();
      ....
private:
     std::vector<Node*> m_path;
}

void walkPath() {
   if(m_path.size() >= 2) {
        walkToNode(m_path.at(1));
}
 

Now for each new NPC I create, I create a thread managing the path calculations
Thread

class Thread {
private:
    m_player;
    m_enemy;
}

void Thread::run() {
    sf::Mutex mutex;
   
    mutex.lock();
   
    std::vector<Node*> path = findPath(m_enemy, m_player);
    m_enemy->setPath(path);
   
    mutex.unlock();
}
 

that's a pretty rought sketch, but you see what I mean.
Also, with the walkPath method, I just always walk to the second element because, by the time the enemy gets there, i'll probably have a new path, calculated from the node the enemy arrives on and just goes from there

Right now, the program just crashes when I use the thread instead of calculating the path each frame due to a segmentation fault. I don't know what I'm doing wrong...

Please help me, thanks!

9

General / Re: [Weird] Linking problems

« on: December 16, 2012, 01:42:38 pm »

I tought SFML 2 was still in beta?

No, there is a release candidate. And you can get the newest sources from GitHub.

I suggest you try it with SFML 2, because the 1.x versions were not designed with CMake integration in mind. For example, the FindSFML module has been written for version 2.

Using SFML 2 indeed solved the problem!

10

General / Re: [Weird] Linking problems

« on: December 16, 2012, 01:05:44 pm »

I tought SFML 2 was still in beta?

No, there is a release candidate. And you can get the newest sources from GitHub.

I suggest you try it with SFML 2, because the 1.x versions were not designed with CMake integration in mind. For example, the FindSFML module has been written for version 2.

thanks, i'll give it a shot!

11

General / Re: [Weird] Linking problems

« on: December 16, 2012, 12:21:32 pm »

Yes, I do so in my src/CMakeLists.txt

set(CMAKE_MODULE_PATH "../cmake_modules/" ${CMAKE_MODULE_PATH})
find_package(SFML 1.6 REQUIRED system window graphics network audio)

No, you don't. What you do is finding the package, not linking. In CMake, you can link with the command target_link_libraries. The command names are quite expressive, aren't they?

And I recommend to start with SFML 2. It has more features, less bugs and is actively developed.

I tought SFML 2 was still in beta? And sorry, I forgot that portion where I actually link it, but it's in there:

#SFML lookup
set(CMAKE_MODULE_PATH "../cmake_modules/" ${CMAKE_MODULE_PATH})
find_package(SFML 1.6 REQUIRED system window graphics network audio)

#Executable
add_executable(${exec_name} ${exec_source_files})

#Libraries
set(project_libraries config engine graphics grid input unit util)
set(external_libraries ${SFML_LIBRARIES})
set(libraries  ${project_libraries} ${external_libraries})

#Libraries Link
target_link_libraries(${exec_name} ${libraries})

12

General / Re: [Weird] Linking problems

« on: December 16, 2012, 12:08:48 pm »

Did you link to sfml-system?

Yes, I do so in my src/CMakeLists.txt

set(CMAKE_MODULE_PATH "../cmake_modules/" ${CMAKE_MODULE_PATH})
find_package(SFML 1.6 REQUIRED system window graphics network audio)

13

General / Re: [Weird] Linking problems

« on: December 15, 2012, 04:58:50 pm »

anyone? *bump*

14

General / [Weird] Linking problems

« on: December 12, 2012, 05:13:50 pm »

Hello, I'm trying out SFML for the first time and everything worked fine, with the example code. So then I started integrating it with my project and came across a really weird problem. So I started with this piece of code:

#include <SFML/Window.hpp>

/*
 * @brief Main function, entry point
 *
 * @return      Exit code
 */

int main() {
        sf::Window window;
        return 0;
}
 

And got the following errors:

/usr/local/lib/libsfml-window.so: undefined reference to `sf::Clock::Reset()'
/usr/local/lib/libsfml-window.so: undefined reference to `sf::Unicode::UTF8Offsets'
/usr/local/lib/libsfml-window.so: undefined reference to `sf::Clock::Clock()'
/usr/local/lib/libsfml-window.so: undefined reference to `sf::Clock::GetElapsedTime() const'
/usr/local/lib/libsfml-window.so: undefined reference to `sf::Unicode::UTF8TrailingBytes'
/usr/local/lib/libsfml-window.so: undefined reference to `sf::Sleep(float)'

Now, I 'fixed' it like so:

#include <SFML/Window.hpp>

/*
 * @brief Main function, entry point
 *
 * @return      Exit code
 */

int main() {
        sf::Clock testClock; //this fixed the problem???!!!!
        sf::Window window;
        return 0;
}
 

it builds fine, no errors at all...

Someone please help me?

By the way, I'm using SFML 1. 6 on an Ubuntu machine