Yeah, handling negatives is tricky. At the risk of hijacking a thread AND giving away all of my tricks… 
[java]
public static int worldToLeaf( int i ) {
if( i < 0 ) {
// Need to adjust so that, for example:
// -32 to -1 is -1 instead of part -1 and part 0
i = (i + 1) / LEAF_SIZE;
return i - 1;
} else {
return i / LEAF_SIZE;
}
}
[/java]
worldToNode() does a similar thing but with NODE_SIZE instead.
Aw ok, so my thought of need to convert negatives in any way, was not wrong^^
I thank you very much : )
@solidleon I understand your questioning but please, next time, start a new thread (referring the relevant post in the thread) or contact the person you want the answer from in a PM.
Well well. The caching system works! 
Except for the fact that it tries to cache EVERYTHING, which it shouldn’t.
I guess all the beer I took during the weekend and the coding following that broke my “look up” algorithm. 
Surprisingly even at 3 priority, it looks like it’s pretty fast and isn’t giving any hint of being too intensive/hard. The CPU running the thread is running a lot more than it used to though. The good news is, I wasn’t able to see any side-effect visually. Actually, rendering, if anything, is faster. FPS is higher and churning seem to have improved (in a very good way).
Really happy now.
The caching system work at 95%+ in a static fashion. By that I mean when the ship is immobile. For now this is by design. Updating the cache as we move around isn’t implemented yet.
The only noticeable mis-caching issue are when the player finds itself in a huge leaf that is adjacent to much smaller leafs. Since the leafs are not linked (a la linked list or similar) I have to look them up based on a position vector. That weirdness of having very small leafs beside a huge one is extremely rare. It actually happens only in a barred galaxy where the bar meets the starting point of an arm. That part of the barred galaxy I wanted to fix anyway, so that should fix both issues.
The way the caching works is that at each loop, if there is no AI and no Game command, the game will work on the cache. Each looping will do something once (add a leaf, generate the systems in a leaf which hasn’t its systems done yet, etc) until everything is done and saved.
For those interested, the cache is separated in three main LinkedHashSet. Front, middle and back. But, because the ship can mode in 3 directions I plan to add two other sets that will cover up/down and “sideways” movements. If you’re wondering why, the answer is: It should be a lot faster to shift the hash sets in a given direction then add the missing leafs than having to start from scratch. In short, if you move “forward”, your old “forward” hash set will become your “middle” (less the current leaf) the “middle” set becomes the “back” set (plus the old leaf you were in) and then query the missing leafs.
Filling the other “direction” hash sets should be trivial by using layers of the other existing sets.
@Madjack - grats on your work! I have similarly vast goals, so I appreciate your vision. Maybe after I stop being a jMonkey noob we can trade notes
One thing you should check out, if you haven’t already, is Infinity. (http://www.infinity-universe.com/) It’s an MMO in development, which has a MASSIVE procedural galaxy. It’s incredible just to watch some videos of what they’ve done. But, they also seem to be quite open about their tech. Running through their website you can get a good overview of how they approached the problem, and digging through their forums you can get some really in-depth information on how they’ve specifically architected certain aspects. Lots of fans ask questions about Infinity itself out of curiosity, or even ask advice for their own garage projects, and I’ve noticed admins posting answers pretty regularly.
Good example, and without having much knowledge in the area, might even help you out on your specific questions this post: http://www.infinity-universe.com/Infinity/index.php?option=com_smf&Itemid=75&topic=12345.0
Reading through some of this stuff wishes I spent 8 more years in math
Thanks for the kind words @jelamb
I did visit Infinity Universe’s site when I started the project, it has nice info there. The game looks very nice and interesting, at least the last time I went there and watched the videos. I’m sure it didn’t go downhill since then. Unfortunately I don’t visit there now because I’ve got a vision of what my game should look like and I wouldn’t like to plagiarize, even without the intent to, what they are doing. I respect other people’s work too much to do that. Of course I might end up doing some things in a similar way, but I will know deep down that it was just a coincidence or maybe the best route and we’ve come to the same conclusion?
Just so you all know, -length != length
Now the caching catch all the right leafs. Yay! I know I said I could live with that, but I lied I guess.
Question following…
I’m pretty damn proud to announce that the caching system now works as intended. Yay! It gets updated when the ship switch leaf and I even made a debug flag that will show these cached leafs on the game world.
Question. It worries me that I have to pause the game thread for about 150 ms to get the correct result from the thread taking care of the cache. If I don’t, I’ll always get the "old list’ of leaf ids from which I draw the outlines.
Here’s the code.
in the Update() of the GalaxyScene (An AbstractAppState), I do some magic then finally call the following method:
[java]
[…]
private void drawCachedOutlines() {
synchronized (this) {
try {
wait(150);
} catch (InterruptedException ex) {
Logger.getLogger(GalaxyScene.class.getName()).log(Level.SEVERE, null, ex);
}
}
deleteDebugOutlines();
// Debugging cache boundaries.
debugCorners(gMgrs.getGameState().getNodeID());
debugCacheBoundsSpheres(gMgrs.getLeafManager().getDebugSpheres());
outlineCachedLeafs();
}
[…]
[/java]
I’m wondering if a Callback method (using an interface (I read about that today)) should be used to draw the debug outlines. For the normal outlines this isn’t a problem as the data is always in the leaf itself when it is loaded. But then again, I’m thinking since this is only for debugging, maybe a wait isn’t that much of a problem. But on the other (thirds hand?) hand, knowing how to cope with these situation in the future would help I guess.
Expect a new video showcasing that cache soon.
I can understand your distaste for the wait. In general, in modern Java a “synchronized” or a “wait” should make a developer a little uncomfortable in performance critical code given all of the great classes in java.util.concurrent. Though for developers new to threading and/or Java it might take a bit to understand the nuances.
There are sort of two ways to handle this situation which I will describe from a high level because to go into more depth requires more information than we’ve been provided.
- Asynchronous events: the render thread spins away using whatever data it last had. The background thread enqueues a Callable with the Application that gets called on the next update pass. The callable swaps out the old data for the new. The callable in this case can be thought of like an event.
- Shared buffered data: the render thread spins away using whatever data it last had, it also checks to see what is in the shared buffer. If the stuff in the shared buffer is newer than what it has then it swaps them out.
These are sort of high level general “frameworks” for the real answer… and they can slide around a bit. For example, Mythruna uses something like the first one for its tile rendering. A pool of worker threads render the tiles and stick them on a “done” queue. The render thread pulls at most one item from the done queue per frame and applies it. (if it were to apply them all then there would be really noticeable frame drops).
On the other side, avatar positions are done using something like the second one. Each avatar has a buffer using a sliding window of time indexed position data. The networking thread sticks new position data onto the end of the avatar’s buffer, timestamped appropriately. The render thread then finds the appropriate interpolated position for the time that it is currently rendering. This is about as complicated as it gets and I use a hand-rolled data structure for that one versus something from java.util.concurrent… but a) I sort of know a lot about Java’s threading architecture, b) I still always assume it’s the source of any bugs I find.
Simpler shared buffer strategies are where you use AtomicReference to share an object (or many atomic references) and the worker thread sets the reference and the update thread checks it. For example, if I didn’t want smooth avatar movement, I could have kept one AtomicReference per avatar holding the last position data… and then only moved the Spatial when the spatial’s position was not equal to the current position.
Why someone would want to use AtomicReference over just using an unsynchronized shared variable in this case gets into a deeper more confusing conversation about threaded memory models, etc… And simply “synchronizing” access can be a performance issue. Synchronized has a decent amount of overhead when there isn’t any contention… and potentially a LOT of overhead when there is.
Sorry for rambling… hopefully this is not a retread over stuff you already know.
2 Likes
As usual, thank you @pspeed for your enlightened post.
At one point I was using a “reference” class that was holding time-critical information, or so I thought. It wasn’t really needed so I dropped it. Maybe I should use an atomic reference for that list of IDs and see how that works. This would be more of a personal test as, I mentioned, this is only debug code, it’s not a big deal and will be “removed” at release. Still, I’m sure I’ll run into other similar problems down the road and this could be one of the solution to solve them.
As for the Callable, I remember reading about that. I might look that up again, just to be aware of its existence and how to use it. You know, for future reference.
I think, as many people, I find myself with a good basic understanding of the language but hit a dry well when looking for some solutions because of the great number of packages the language itself offers. When you’re not used to use this or that package, it’s often hard to know of their existence. Even if you know about them, properly using them is another whole affair. That’s where experience comes into play. And we all know threading can be cumbersome for many users.
Yeah, re: the experience. Threading can be weird too, anyway. I’ve read various articles over the years complaining about this odd thing or that odd thing and at first was like “No, that can’t be true” until you really dig into the memory and threading architecture and find out that it IS!
For many years when all Java had was Thread and synchronized/wait/notify, Doug Lea was who we turned to for guidance and clarity… and finally the java.util.concurrent package came incorporating most of his stuff right into core. And still I haven’t had a chance to go through all of it… but it’s really good stuff.
Reading and posting these days have made me realize I shouldn’t have left programming 14 years ago. 
I was younger and dumb… I’m still dumb though.
It’s definitely easier “growing up with” some piece of technology like Java than it is trying to swallow it whole. My first full time work doing a full Java application was targetting Java 1.2 while it was still in early beta. Circa 1998 or something.
It’s a little easier to learn the new parts as they are added… especially when you have been anticipating them for some years prior.
If you feel like it, you can answer the following.
Given that I use a HashSet of Integers to store the leaf IDs that compose the cache.
When the player ship switch leaf, I call a method in the LeafCache class to trigger the “Game Thread” to find the new adjacent leafs (This is actually a flag). The thread, seeing that the flag has been raised, then calls a method that uses the algorithm that I devised to store those IDs in listLeafsID (the HashSet). Note that this is almost simultaneous, as it should be since it’s a flag and the game thread is running the idle methods once every frame to check if there’s work to be done while the LWJGL thread does it’s thing (That’s the thread that calls the method that raises the flag).
Shortly after the flag has been raised by the LWJGL thread, it calls the method I pasted in the previous post above. In that method, it’s outlineCachedLeafs(); that fetches and draw the outlines:
This method is in GalaxyScene.java
[java]
private void outlineCachedLeafs() {
for (Integer i : gMgrs.getLeafManager().getCachedLeafIDs()) {
if (i > -1) {
Vector3f[] vecCoords = gMgrs.getLeafManager().getLeafCoordForOutline(i);
makeBox(vecCoords[0], vecCoords[1].add(-.0125f, 0.0125f, 0.0125f), ColorRGBA.Blue, “Debug Outline”);
}
}
}
[/java]
This method is in LeafCache.java
[java]
@SuppressWarnings(“unchecked”)
public synchronized Integer[] getCachedLeafsID() {
Integer[] array = new Integer[listLeafsID.size()];
listLeafsID.toArray(array);
System.out.println("Returning array : " +listLeafsID);
return array;
}
[/java]
The point of contention here might have to do with the way I draw those outlines. Meaning that, once I’ve triggered the change of leaf, I take for granted that I received the right IDs. In short, I delete the “old” outlines then draw the new ones ONLY ONCE. That decision was made based on the fact that once it’s in the scene graph, there’s no need to delete and redraw those if they haven’t changed. A good (and probably a right) assumption IF the data is accurate, which it isn’t in this case.
listLeafsID is defined as:
[java] private final Set listLeafsID = Collections.synchronizedSet(new LinkedHashSet<Integer>());
[/java]
No matter if I set that HashSet as volatile, synchronized, final or otherwise, if there’s no wait on it, I’ll always get the “previous” values. Next step might be to try Atomic if I can make it work with a HashSet.
What I believe is happening after a quick read and only what was provided…
Presuming you set the flag and pretty much immediately launch into trying to grab the IDs, I suspect that you’ve locked the listLeafsID in the toArray() call so that your background thread cannot touch it until that returns. By waiting some arbitrary amount of time you allow the background thread to get the lock first.
…and if that’s not the case then your wait() may randomly fail if for some reason the the background thread takes longer than 150 ms… but I doubt that’s the issue.
A little logging might confirm this.
Can I ask how your background thread is polling the flag? Is the flag volatile or an AtomicBoolean or just a plain old field, synchronized?
Another way to do this (if I’m reading it right) would be to have a ConcurrentLinkedQueue that the background thread feeds new IDs to. The lwjgl thread then need only poll this queue for IDs… in a loop, one at a time, or whatever depending on how many you want to handle per update(). Basically, if your leaf cache gets a new ID then it just adds it to the queue.
I don’t know how you handle expiration in the scene graph or the cache so I can’t comment on whether there is a more unified approach or if its even necessary.
pspeed said:
Presuming you set the flag and pretty much immediately launch into trying to grab the IDs, I suspect that you've locked the listLeafsID in the toArray() call so that your background thread cannot touch it until that returns. By waiting some arbitrary amount of time you allow the background thread to get the lock first.
That, but not quite. I think what happened is that the main game thread queried those ids before the background thread had the time to go through the iteration and come up with new ids. Or because it's doing something else like generating solar systems or saving leafs.
I've come to that conclusion by completely reviewing the idea of when I should get those ids. As I explained above, what I was doing was set the flag then, maybe 10/15 lines later (mostly boolean checks), I'd query those ids.
Now, what I do is I set a volatile boolean "hasNewIds" variable (that is synchronized in the methods where it's accessed) in the leaf cache to TRUE as soon as that new list is generated. In the GalaxyScene, instead of assuming anything, I query the cache to know if the new Ids are ready. If not, I go on my merry way until I come back to it on the next frame and check again until I finally draw the new outlines. That "hasNewIds" variable is then reset to FALSE after the main thread has successfully retrieved the new list of Ids.
After a couple of tests, this seems to work although I have seen a "hitch" where it took maybe a second to get the new ids and have them drawn on the screen.
Howabout using a Semaphore?
Spawn a thread to draw them that waits (aquire on the semaphore) untill the Cache is finsihed (and calls release on the Semaphore) . Semaphore operations are guranteed to be atomic, so this should work.
1 Like
That’s a great idea! I didn’t think about that.
I will definitively look up how easy and convenient it would be to use that later.
Thanks!