Jump to content
  • Advertisement
Sign in to follow this  
menyo

Threaded pathfinding on dynamic tilemap

This topic is 1046 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am playing with the idea and already did some tests on having pathfinding run on a separate thread. I am very new to threading and I want to explore the possibilities of this since in the game I have in mind I do not need immediate paths. The player does not control units directly but issues orders through the interface. Something like the game Settlers does :

  • The player places a building and a unit with the building job enabled can get a order from the building to construct it.
  • The player issues a stockpile to store weapons the stockpile looks for the nearest item and finds a Idle unit preferably nearby with the hauling job enabled.

Now as I understand dynamic and threading are conflicting with each other. I cannot issue all these order simultaneously since unit A might go for the same item as Unit B and things will obviously break. How can I deal with this in a proper way? This is what I am thinking off:

  • Stockpile needs item.
  • Stockpile issues a Thread to lookup the item.
  • Thread goes to work.
  • Stockpile needs another item.
  • The thread is still running so it cannot issue another order yet.
  • Thread has finished the job and marked the item as unavailable.
  • Stockpile notices that the Thread is finished and can proceed with the next item.

When an order is cancelled or perhaps the unit has died or the item cannot be reached anymore the item becomes available again. I will also have a list for each type of item so I can have a thread that looks for food and one for weapon run simultaneously. So basically I will have a single thread for each job that handles dynamic data running at a time.

 

Since I am new to Threading I have no idea what to use. In the passed I have dabbled a bit with FutureTask and custom Callables. Should I create a Thread for each of the needed tasks and wait for them to finish? Perhaps I can create a listener to notify when a Thread has done it's job? Is there already build in functionality for this in Java or a library that is compatible with LibGDX desktop? Is this even a good idea or should I drop this whole concept?

Edited by menyo

Share this post


Link to post
Share on other sites
Advertisement

I haven't implemented this system myself but my approach to this would be as follows. Queue updating the pathing graph until all current searches for paths are complete (this will result in some now invalid paths but we'll get to that). Queue any additional path requests after the graph update. So you finish what you are currently working on but don't add any more until the update is complete. That will leave you with the potential for some invalid paths but is that so bad? a Unit will try to path along it and come to an edge which it can now no longer pass, in which case it just tries to find a new path.

Share this post


Link to post
Share on other sites

Great read Rip-off!

 

The problem is I cannot queue up much tasks. Say a building requires 2 stones. If I would start queuing up these 2 tasks there is a risk the second task is pointing to the same stone.

 

Anyway, I already know I need the threading since I have potentially large maps 6.000.000 tiles and have a lot of experience with pathfinding on these tile maps. I could implement hierarchical pathfinding and that would help a ton on performance but I think it has it's charm when units do not react instantly anyway. I have also done tests on DataStructures and looking up or sorting 1.000.000 items just cannot be done in a couple of ms and these are the numbers I'm aiming for. Just a single battle with 20 units can leave hundreds of items behind. Even if I would cut up everything in chunks there still might be some items of interest all across the map and that would kill performance on the main thread. So to keep the UI responsive threading is afaik the only way.

 

Taking your advice I still have a lot to learn about threads especially about thread safety I guess. But I currently have a working prototype (console app) at the moment where I simulate the behavior I need. The path finding is just simulated by Sleep the thread but the lists of items are "real". It's not thread safe, I have to work on that but I am locking items so they cannot be accessed when being interacted with.

  • Unit 1 is idle and looks for an activity.
  • A building needs to be build that still requires 2 wood and 1 stone.
  • Request a Item lookup for the wood.
  • The thread is ready, the wood item gets flagged unavailable and Unit 1 is on it's way.
  • Unit 2 is idle and looks for an activity.
  • That same building still needs 1 wood and 2 stone.
  • Request a item lookup for wood.
  • The thread is busy so we request a lookup for stone.and get it.
  • Unit 3 is idle, he cant find a job so he goes to the pub to waste himself until a thread is ready.

This is where the looking up is being done, only activities access this. I have tried to work with the thread and task itself but eventually ended up having a boolean busy to mark the thread busy.

public boolean requestLookup(String type, Coordinates nearCoordinates)
    {
        if (busy) return false;
        //if (lookUpThread.isAlive()) return false;
        /*
        if (lookupTask != null)
            if (!lookupTask.isDone()) return false;
            */
        lookupTask = new FutureTask<Item>(new LookupTask(type, nearCoordinates, items));
        lookUpThread = new Thread(lookupTask, category + " lookup thread");
        lookUpThread.start();
        busy = true;
        return true;
    }

    public Item getItem()
    {
        if (!lookupTask.isDone()) return null;

        try {
            busy = false;
            return lookupTask.get();
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }

        System.out.println("Item lookup failed");
        return null;
    }

This is in the class ItemLookup and each item category will have such a class firstly to release the strain on the lookups since I will have a lot of items and when looking for stone I am not interested in weapons. Secondly, I can have more threads running simultaneously. I will implement a ExecutorService for the tasks with a thread pool to eliminate the overhead of creating threads.

 

While this seems to be working there is a lot more room for improvement and thinking. 

  • Whenever I place a building or a task that requires multiple items I could look those items up together and mark these for retrieval within the building.
  • Perhaps I could have the thread wait for a view seconds and lookup a lot more at once. For example to lookup an item I need a flood fill. Say 100 stones are needed I can potentially do this all in a single thread.

Share this post


Link to post
Share on other sites

Anything that occurs more often than once every 10-15 seconds and involves the words new Thread is bad. Try not to do that. Not only is creating threads a possibly very expensive operation that may unexpectedly stall your main thread, but also you do not have much of a control on how much concurrency there is.

More is always better, but not so with threads. Every thread must have a stack of its own, and every additional thread causes context switches and competes over cache and TLB. Java is not aware of these hardware details and pretends that they don't exist, but that doesn't mean they aren't there. You want the minimum amount of threads possible to use up all your CPU's cores (with hyperthreading that's usually at least one fewer thread than there are cores). You never want to fire a previously unknown number of threads.

 

Instead, since you already think in tasks, push tasks to a queue and have a fixed-size pool of threads pull tasks. Have dependent tasks be pushed upon completion. Keep some information "global" read-only (only modifiable by the main task), and push anything that can benefit from running in parallel onto the queue. Tasks never write to global state concurrently (this requires a lot of synchronization and is hard to get right) but return results via an identical mechanism (synchronized queue), and they signal completion via a semaphore/event or a similar mechanism.

Wait for completion (block) and then do the "global" management things that would be hard to get right in parallel or that would require an excessive amount of synchronization in the main thread.

 

Something like this:

 

Each simulation step, if a player has given a command (like "build house here"), push two dependent k-nearest neighbour search tasks on rocks and on units (first, find all-k rocks nearby some given locations, second, find all-k units near the found rocks). The query for rocks should only consider the ones that are not already taken, obviously (that can be done with a simple flag). In your example of wanting two rocks to build a house, it is probably a good idea to search for the nearest three rather than two, so you have the possibility to choose alternatives in case there are several competing requests, but that's not necessary.

If any AI players want some too, then do the same thing as for the players (only with the AI's units).

 

Sync (wait) on the main thread, and look at results. Here you decide who gets to take which rock. No conflicts possible. This is not very CPU-intensive, so it's no biggie to run this single-threaded. It however makes conflicts impossible and greatly simplifies the logic (the synchronization that would otherwise be necessary would likely eat up anything gained from threading anyway).

 

In your global list of "available rocks", for each rock that you decide to "take", set the per-player "available" flag to zero, so other units from the same player will not try to grab the same rock. Note that this will not prevent units from different players to compete for the same rock, but that is OK (actually desirable!). As you set the "available" flag to zero, create a corresponding "pathfind" task for the closest unit that fires off a dependent "move to" task upon completion, firing a dependent "grab it" task upon success -- and a "report failure" task if an enemy unit has already mined the rock when the unit arrives, or if the unit gets killed on its way. The latter one is important so you do not "lose" rocks -- you've cleared the "available" flag so you won't reconsider that rock again. So, if a unit is killed, the "failed, dead"  task makes sure you react appropriately. You might for example fire two tasks to react to this: One "pathfind" and "go-to" and "grab" task to the next worker unit, and one "pathfind", "go-to", and "kill" task to the nearest soldier unit. Or, anything you like, as long as you make sure you don't "lose" the rock from your mind. The task queue will magically run these in parallel.

 

As an optimization, if a task fires a single dependent task (that also depends on nothing else) you can usually (not always, there's edge cases where this will cause some artefacts) just execute it instead of pushing it to the queue again, by the way. But simply pushing any new task to the end of the queue works fine and is logically correct.

Edited by samoth

Share this post


Link to post
Share on other sites


The problem is I cannot queue up much tasks. Say a building requires 2 stones. If I would start queuing up these 2 tasks there is a risk the second task is pointing to the same stone.

Then you can make the tasks a bit higher level, such as "find the nearest N stones to location X, Y", or as samoth suggested create a task dependency system, where the second search is not attempted (or queued) until the first one has been actioned (e.g. the stone has been reserved).

 


Anyway, I already know I need the threading since I have potentially large maps 6.000.000 tiles and have a lot of experience with pathfinding on these tile maps. I could implement hierarchical pathfinding and that would help a ton on performance but I think it has it's charm when units do not react instantly anyway. I have also done tests on DataStructures and looking up or sorting 1.000.000 items just cannot be done in a couple of ms and these are the numbers I'm aiming for. Just a single battle with 20 units can leave hundreds of items behind. Even if I would cut up everything in chunks there still might be some items of interest all across the map and that would kill performance on the main thread. So to keep the UI responsive threading is afaik the only way.

Remember that multi-threading can only yield a maximum of linear performance gain over single threading, based on the number of execution units on the end-user's machine. Algorithmic changes can have dramatically better gains.

 


... but I think it has it's charm when units do not react instantly anyway.

You can always add a tunable delay between when the information is known and when it is acted upon to get the same behaviour.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!