Sign in to follow this  
boogyman19946

Too many thread instances [Java]

Recommended Posts

boogyman19946    1487
Hello everyone! I've been working on a game for a while now (actually I've been working on it whenever I feel like it and Netflix usually gets the best of me T_T) and a large portion of it is now done. The latest portion of the game, pathfinding, has been giving me some trouble. The game is a 2D platformer in the style of Thing Thing Arena (ish) so the pathfinding involves zombies hopping their way to the player and keeping track of their path if they fall through fragile floors and such. The functional portion was a hassle but it was doable (although it's still uber buggy). The problem arises when multiple zombies end up in the level and every one of them needs to find a path to the player: the game comes down to a crawl. I thought I'd solve the problem with multi-threading so I wrapped the pathfinding function in a thread and that actually solved the problem. Now another problem came to life.

Since Java doesn't allow stopping and reviving threads (or at least I wasn't able to figure out how to do that), I would have to either keep one thread running at all times with switches (and sleep commands when it's not active), or create a new instance every time I need to find a new path. The second one is problematic since with about 30 zombies roaming the level, every time I switch a platform, 30 new thread instances are created. I've ran the game through a profiler in NetBeans and the thread count goes well into the thousands until I get an exception that tells me there is no more room for more threads and the game crashes. This leaves the option of starting the thread in the constructor of the pathfinding class and controlling it with member variables.

So the question is: is it acceptable to have the thread running all the time checking if it needs to find a new path? (kind of like the game loop that checks for input) Or is there a better way to parallelize the pathfinding?

This is my first time using multi-threading. It's definitely an interesting experience.

Share this post


Link to post
Share on other sites
beatlefan    198
You shouldn't need to make a thread for each pathfinding function (which is what your doing right?). Perhaps you're calling your pathfinding function to many times or it's really inefficient.

Share this post


Link to post
Share on other sites
Kalten    189
If you have lots of objects i could understand having multiple threads for something like pathfinding... though i wouldnt expect you'd have one per object instance, more likely one per behaviour instance.

To me, thinking logically, its a serial process, by creating it as a paralell process by excessively threading it i'd expect you'd hit all sorts of unexpected behaviour due to the different threads all fighting for the same space on your virtual chess board (figure of speach). I'd expect that if you hone your pathfinding algorithm, making it more efficient, you'll probably find that having all the pathfinding done in a single thread might be sufficient and actually more reliable, after all, you dont want to run the risk of having information in one thread becoming out of date in the middle of the run because another thread has modified some value in an asymetric fashion.


<edit> further thinking...

I'd expect that you want pathfinding allways running... at least doing a check to see if there's any calculation required first, if it is required, calculate, update your path and then move on to the next object.

If you have 30 objects that do not have any pending calculation, or required change, the process will be pretty quick... by profiling your pathfinding algorithm you'll be able to see how scalable you can get it, and if you see any extended times on it, then fork it out to an additional thread.

Share this post


Link to post
Share on other sites
boogyman19946    1487
@beatlefan, It's very possible that the algorithm is terribly inefficient. This is the first game that I made that needed pathfinding. I've created something to the effect of a node graph which is generated by the level designer so that the game itself doesn't have to generate it but rather just navigate it. The algorithm is best described by the Breadth-First Algorithm (keep expanding until the goal is reached).

@Seriphis, The finding of a path is done in a single function. The object calls a function from it's pathfinding module (that's the class that has the function) which checks how the path stands in the current conditions, that is, if it needs to be recalculated or how to proceed to the next node. If a new path is needed, the function changes a boolean value which the thread catches and then proceeds to find a new path. Reference to the currently active path is then updated and action continues. From the suggestions, I'm guessing the efficiency of the algorithm is indeed to blame, so I'll have to revisit it eventually. Meanwhile, I'll go ahead and post the code so you guys can see how the thread is implemented.

[code]

private void PathFindingThread() {
new Thread() {
public void run() {
while(true) {
if(mInitPathfinding) {
mInitPathfinding = false;
mFindingPathmap = true;

final LinkedList<LinkedList<Platform>> tempPaths = new LinkedList<LinkedList<Platform>>(); // rofl linked list inside a linked list XD win!
final int PlayerPlatformID = PlayerPlatform.ID;

// assign starting position
for(int i = 0; i < mOccupiedPlatform.mLinkedPlatforms.size(); i++) {
Platform.PlatformLink tempLink = mOccupiedPlatform.mLinkedPlatforms.get(i);
// Iterate through link cells and add them as nodes
if(tempLink.mGoalPlatform.ID == PlayerPlatformID) { // Goal path
Platform newPlatform = new Platform(mOccupiedPlatform.mDimensions, mOccupiedPlatform.ID);
newPlatform.addLink(tempLink);
LinkedList<Platform> newPath = new LinkedList<Platform>();
newPath.add(newPlatform);
mPath = newPath;
mCurrPathGoal = PlayerPlatform;
tempPaths.clear();
mFindingPathmap = false;
return;
} else {
// Create new single path platforms (there's really no other way to get around this >.>
Platform newPlatform = new Platform(mOccupiedPlatform.mDimensions, mOccupiedPlatform.ID);
newPlatform.addLink(tempLink);
LinkedList<Platform> newPath = new LinkedList<Platform>();
newPath.add(newPlatform);
tempPaths.add(newPath);
}
}

while(!tempPaths.isEmpty()) {
LinkedList<Platform> currPath = tempPaths.pollFirst();
Platform currPlatform = currPath.getLast().mLinkedPlatforms.getFirst().mGoalPlatform;

// Iterate through all the linked platforms
for(int i = 0; i < currPlatform.mLinkedPlatforms.size(); i++) {
Platform.PlatformLink currLink = currPlatform.mLinkedPlatforms.get(i);

int ID = currLink.mGoalPlatform.ID;
// 1. Check if it's the goal platform
if(ID == PlayerPlatformID) {
LinkedList<Platform> nextPath = new LinkedList<Platform>(currPath);
Platform nextCurrPathPlat = new Platform(currPlatform.mDimensions, currPlatform.ID);
nextCurrPathPlat.addLink(currLink);
nextPath.add(nextCurrPathPlat);
mPath = nextPath;

tempPaths.clear();
mCurrPathGoal = PlayerPlatform;
mFindingPathmap = false;
return;
}

// 2. Check if the platform has been reached by other paths
// 2.a Check current path first
boolean done = false;
for(int j = 0; j < currPath.size(); j++) {
if(currPath.get(j).ID == ID) {
done = true;
break;
}

}
if(done) // so much ass. Can't break inside the loop
continue;

// 2.b Check paths in the queue
for(int j = 0; j < tempPaths.size(); j++) {
LinkedList<Platform> otherPath = tempPaths.get(j);
for(int k = 0; k < otherPath.size(); k++) {
if(otherPath.get(k).ID == ID) {
done = true;
break;
}
}
if(done)
break;
}
if(done)
continue;

// 3. Branch out to linked platform
LinkedList<Platform> nextPath = new LinkedList<Platform>(currPath);
Platform nextCurrPathPlat = new Platform(currPlatform.mDimensions, currPlatform.ID);
nextCurrPathPlat.addLink(currLink);
nextPath.add(nextCurrPathPlat);
tempPaths.addLast(nextPath);
}

try {
Thread.sleep(10);
} catch (InterruptedException ex) {}
}
mFindingPathmap = false;
} else {
try {
Thread.sleep(1000);
} catch (InterruptedException ex) {}
}
}
}
}.start();
}

public void Update() {
FindOccupiedPlatform(); // Update Occupied platform
if(mOccupiedPlatform != null && PlayerPlatform != null) {
if(mOccupiedPlatform != PlayerPlatform) { // Entity and goal are not on same platform
if(!mFindingPathmap) {
if(PlayerPlatform != mCurrPathGoal) { // || mOccupiedPlatform) { // Player changed platforms
mInitPathfinding = true;
}

mEntity.mMotionModule.ResetJumpFlags();
if(!mPath.isEmpty()) { // Move along path
Platform checkpoint = mPath.getFirst();
if(checkpoint.ID == mOccupiedPlatform.ID) {
while(true) {
if(!checkpoint.mLinkedPlatforms.isEmpty()) {
Platform.PlatformLink currLink = checkpoint.mLinkedPlatforms.getFirst();
if(!currLink.mLinkCells.isEmpty()) {
Platform.PlatformLink.LinkCell currCell = currLink.mLinkCells.getLast();
if(Math.abs(currCell.mDimensions.x - mEntity.mBoundingRectangle.x) < 2.0) { // this can't be calculated exactly so instead lets calculate a "close enough"
if(mEntity.mBoundingRectangle.y+mEntity.mBoundingRectangle.height <= currCell.mDimensions.y + currCell.mDimensions.height /*height*/) { // 32 = cell height
currLink.mLinkCells.pollLast();
continue;
} else {
if(mEntity.mBoundingRectangle.y+mEntity.mBoundingRectangle.height > currCell.mDimensions.y + currCell.mDimensions.height /*height*/) {
if(mEntity.mMotionModule.mVelocity.y >= 0.0f) {
//System.out.println("Jump");
mEntity.mMotionModule.SetMotion(MotionModule.JUMPID, true);
}
}
}
} else { // Entity hasn't reached checkpoint
if(currCell.mDimensions.x < mEntity.mBoundingRectangle.x) {
mEntity.mMotionModule.SetMotion(MotionModule.LEFTID, true);
mEntity.mMotionModule.SetMotion(MotionModule.RIGHTID, false);
} else {
mEntity.mMotionModule.SetMotion(MotionModule.LEFTID, false);
mEntity.mMotionModule.SetMotion(MotionModule.RIGHTID, true);
}

//System.out.println(Float.toString(mEntity.mBoundingRectangle.y/*+mEntity.mBoundingRectangle.height*/) + ", " + Integer.toString(checkpoint.y));
if(mEntity.mBoundingRectangle.y+mEntity.mBoundingRectangle.height > currCell.mDimensions.y + currCell.mDimensions.height /*height*/) {
if(mEntity.mMotionModule.mVelocity.y >= 0.0f) {
mEntity.mMotionModule.SetMotion(MotionModule.JUMPID, true);
}
}
}
break;
} else {
checkpoint.mLinkedPlatforms.removeFirst();
}
} else {
break;
}
}
} else {
mPath.removeFirst();
}
} else {
mInitPathfinding = true;
}
}
} else { // zombie and player are on the same platform
if(!mEntity.mBoundingRectangle.intersects(PlayerPosition)) { // If zombie not within range of player
if(mEntity.mBoundingRectangle.x < PlayerPosition.x) { // Move to player
mEntity.mMotionModule.SetMotion(MotionModule.LEFTID, false);
mEntity.mMotionModule.SetMotion(MotionModule.RIGHTID, true);
} else {
mEntity.mMotionModule.SetMotion(MotionModule.RIGHTID, false);
mEntity.mMotionModule.SetMotion(MotionModule.LEFTID, true);
}
} else {
mEntity.mMotionModule.SetMotion(MotionModule.LEFTID, false);
mEntity.mMotionModule.SetMotion(MotionModule.RIGHTID, false);

// ATTACK!!!! :D
}
}
}
}[/code]

There are two functions in one class (one instance class for every zombie so each zombie gets it's own pathfinding module, but the node graph is static). The Update() function gets called to perform various checks.

Thanks guys for your replies!

Share this post


Link to post
Share on other sites
Ashaman73    13715
In general, instead of using many threads it is better to use only a pool of worker threads and a dispatcher. The dispatcher is in fact only a queue of requests, the dispatcher takes a look at the queue and will delegate the request of any free worker. The worker will do the job and went inactive afterward.

For your java problem, you can use notify/wait on an object instance to control a thread, simple example(pseudo):
[code]
class WorkerThread implements Runnable {
// job is an simple interface, i.e. a pathfinding job
private Job job;
private boolean dontExit = true;

synchronize public void sleepNow() {
// TODO: handle interrupted exception
this.wait();
}

synchronized public void wakeUp() {
this.notify();
}

synchronize public void setJob( Job myJob) {
this.job = job;
}

synchronize public stop() {
dontExits = false;
}

synchronize public void isFinished() {
retrun job!=null && !job.isFinished()
}

public run() {

while(dontExits) {
if(!isFinished()) {
// execute job
job.execute();
} else {
// nothing todo, sleep
sleepNow();
}
}
}

// control example:
Job myNewJob =...
for( WorkerThread worker : myWorkerThreads) {
// check for free worker
if(worker.isFinished()) {
// found free worker
worker.setJob(myNewJob);
// wake up now
worker.wakeUp();
// done
break;
}
}

[/code]

Share this post


Link to post
Share on other sites
brx    720
Actually, Java even offers to take over the whole management of the thread pool: java.util.concurrent.Executors. This way you don't need to manage the sleeping and waking up of the threads yourself.

Example:

[code]
class Pathfinder implements Runnable {
@Override
public run() {
// pathfinding stuff
}
}

// A simple ThreadFactory class (note that it will only be used when no more threads are available:
public class SimpleThreadFactory implements java.util.concurrent.ThreadFactory {
@Override
public Thread newThread(Runnable r) {
return new Thread(r);
}
}

// initializing the thread pool (the executor):
ExecutorService mThreadPool = Executors.newFixedThreadPool(mThreadPoolSize, new FSshThreadFactory());

// starting a new pathfinder:
Pathfinder pf = new Pathfinder();
mThreadPool.execute(pf);
[/code]

Share this post


Link to post
Share on other sites
boogyman19946    1487
I had no idea there were ways to stop and revive threads, but then again, these aren't exactly the most logical places they could be, considering there is a whole Thread class where the commands stop resume and suspend where all deprecated.

I'm also going to have to look at the executor at some point. I've never seen those before.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this