So i'm writing a tile based rpg where all of the NPC's roam around and are governed by their own threads. I'm thinking about having it so that when they enter a certain tile then some sort of semaphore like construct comes up that lets it so that only process can access the contents of a tile at a time. Of course the obvious question is, what happens if NPC is A is going from tile U to tile V, at the same time that NPC B is going from tile V to tile U? What's the most elegant way to handle such a type of situation?

Quote:What's the most elegant way to handle such a type of situation?

Not using threads at all.

Have NPCs store their path and target. Then update that in single, probably main thread.

The computationally expensive part will be calculation of path, and perhaps there might be gains of running that in separate threads.

In addition, if pathfinding needs to consider dynamically moving objects, then the simplest way is to operate on snapshot only. Each time you need to update the paths (for one or more NPCs), store entire state. Have threads calculate new paths, and store it.

On each tick the movement is then update for the most recently calculated paths. Since it's single threaded, it avoids the race condition of who enters the tile first. It can be first-come first-served basis, or there can be some other rule.

Unique thread assigned to each NPC is not the way to go, the context switch and synchronization overhead of threads will become larger and larger as the number of NPCs reaches a reasonable amount, and it will do more harm than good to your application.

Regarding to your other problem, you might want to check whether the neighboring tiles are occupied as well instead of making an NPC wait for just a single tile.

Quote:Original post by xylent
Unique thread assigned to each NPC is not the way to go, the context switch and synchronization overhead of threads will become larger and larger as the number of NPCs reaches a reasonable amount, and it will do more harm than good to your application.

The threading could be implemented as cooperative model, which is frequently the case with AI. The overhead of context switch there is ~20 instructions. But even though this solves the technical problem, it doesn't solve the conceptual problem of having concurrent computations on shared state.

Shouldn't the first thing to decide be: what do you want to happen ? before asking how to achieve this goal.
In such case the 2 NPC might:
- swap places
- bump into eachother (with a result)
- do nothing
As someone pointed, it would be interesting to know why a NPC wants to go on the tile where another is. He could be assuming the other will leave, but should consider such problems then.

The reason the threading works so easily for me is because of the scripting. This is the first time i'm using scripting in a video game and it seemed like a trivial way to handle npc's would be to define their scripts like so


(define (npc-movement)
(move npc 'right 2)
(move npc 'left 2)
(npc-movement))

I would definetly be interested to see a better way to implement this both with or without threads, I had no idea that their would be a gigantic overhead using this method. I will also be looking into cooperative threading. But still the problem remains ... Let me rephrase it though:

So i'm writing a tile based multiplayer rpg where all of the users are obviously free to roam around wherever they want. I'm thinking about having it so that when they enter a certain tile then some sort of semaphore like construct comes up that lets it so that only process can access the contents of a tile at a time. Of course the obvious question is, what happens if user A is going from tile U to tile V, at the same time that user B is going from tile V to tile U? What's the most elegant way to handle such a type of situation?

Edit: I looked it up and with 100 npc's doing very simple moving and mostly sleeping, it takes up 70% of my cpu. I would definetly like to know how simple run of the mill rpg's do it while also having very simple scripting commands for letting them move around specified or random paths.

[Edited by - caleb_yau on March 3, 2009 7:09:36 PM]

If you want to keep NPC moving blindly, and keep using threads, you can:
- use a timeout like noxis said. you'd still have to handle the case, though
- maybe use semaphores not only for the tiles but also for the tile-pairs
- establish an order for your ressources (semaphores), to prevent the deadlock
But this will not improve your cpu usage.

Right I like the timeout idea a lot. I will keep looking for some way to script movement in the meantime, I'm sifting through kq code as I speak.