[Threading] findPath

[tavrin]

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!

[cire]

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.

[eXpl0it3r]

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.

[tavrin]

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()?

[tavrin]

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

[eXpl0it3r]

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

If you have some problem with your school projects, it's often a good idea to consult the teacher...
As for your laziness in doing some research on path finding algorithms, I can't help you.

For the problem shown the possible 'solution' has already been given by cire.

[FRex]

void Stroustrup_Time()
{
std::cout<<"Sorry. I don't do (other people's) homework."<<std::endl;
}
 

http://www.stroustrup.com/bs_faq.html#homework

Sorry.. I couldn't keep myself from doing that..
Anyway, threading is probably way more complex than algorithms(for which you can google pseudocode), since it craps on the basic rule of things happening in code till now: only one at a time (at least it felt that way for me). Maybe you shouldn't run the pathfinding each frame? I mean, how much can your things move in a reasonably high fps game(~60, limited by avoiding tearing, but still making each frame last very little)? Almost surely not far enough to invalidate their path instructions from the last frame?

However, if you insist on threads, I understand the pain of uni(Grr..evil uni ) and here is a small explanation, hope I didn't make any mistake, I'm quite new to threads and I didn't need them so far:
sf::Mutex when locked stops thread if it's already locked by another thread, so you'd want to do something along the lines of:
Have a function that can change some data in a class, with sf::Mutex as a member of that class, constructing a lock on sf::Mutex while you enter that function. The idea is to have any writing happen during sf::Lock's lifetime.

Another use of threads I've seen is creating several threads to process unrelated data, instead of counting 3 vector sums, each with bilion elements, one after another, we create 3 new threads, tell them to do that and give us back the result somehow and launch them from main thread and imidiately tell them to .wait() so that our main thread waits till all three are done, and then display the 3 sums.

You should really consult documentation of both SFML and/or <thread>(if using a c++11 compiler, <thread> is more powerfull than what SFML offers). Googling your questions about threads or algorithms might help too.

[tavrin]

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

[FRex]

Call it in a thread so it runs during these two seconds(maybe? I don't know what your algorithms work with and what's the result).

[binary1248]

I'm curious, are you sure that your implementation of your path finding algorithm is optimal? Because I have to use them all the time and they can handle 10000+ nodes in a few milliseconds. Can you provide your pathfinding code for download or in pastebin? Maybe I can point you in the right direction to make it faster.

[tavrin]

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)

[eXpl0it3r]

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)

Well if you can show them that you are the one who posted it, they can't do anything about it.

Also it's an algorithm which can not get patented or anything, so it's allowed to copy those ideas from anywhere, as long as you specify from where you got it. - Also Everything is a remix...

[FRex]

Well if you can show them that you are the one who posted it, they can't do anything about it.

Just crap on him untill he does that or make huge fuss without waiting for his explanation and then he'd have to make even bigger fuss and report it to someone who sits higher in the hierarchy than the person that crapped on his grades for using that 'stolen' algorithm in the first place.
+bunch of other things that could happen instead of or in parallel to this scenario.

[binary1248]

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.

[Nexus]

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.

Are you sure?

For std::vector, the iterator can be optimized to a pointer, therefore element access is as fast as possible (1 dereferencing). The index operator may also consist of an addition, so it is certainly not faster than the iterator. In practice, both will have more or less the same performance.

For std::deque, I could imagine that the index operator needs to dereference an additional indirection every time, because of the "array of arrays" structure. The iterator may theoretically keep a direct pointer to the element, so that increments become slower, but dereferencing is very fast.