Java-Gaming.org Hi !
Featured games (81)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (119)
games submitted by our members
Games in WIP (576)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Multi-threading and Collision Detection  (Read 5307 times)
0 Members and 1 Guest are viewing this topic.
Offline philfrei
« Posted 2012-03-09 04:41:50 »

I've been learning about concurrency and Actors, and just got a test program working.

http://www.hexara.com/pond.html


On this program, there are 576 threads (one for each of the squares) running independently. Each with the following basic structure:
1  
2  
3  
4  
5  
6  
While(true)
{  
   
   move();
   Thread.sleep(sleepAmt);
}

I made the sleep amounts different for the different threads. Instead of a game loop, there is a timer() that triggers a redraw every *25* msec, taking a "snapshot" of the current state.

I'm using an array that matches the display, one element per pixel, for collision detection. I've never done collision detection this way before, by locking and consulting elements that correspond to the pixels. (These squares are 8x8 pixels, so there are 64 "drips" in the "pond" that are locked and inspected with each move.) But it seems to make a certain philosophical sense. Space itself is the medium by which we determine what is close and what we can occupy or not.

This structure can also be thought of as a sort of "message passing" medium for the "Actors". When they probe a position, they can find out whether and what other Actor is there, and response behavior can be defined for the situation. For example, in the case of collision, compute a bounce. Or maybe reds can eat oranges or blob together with greens. (One could certainly animate sprites in this context.)

I'm used to reading about things like QuadTrees or Bins. In those cases, one is consults and checks against lists of other objects. Here, one is consulting the space itself. Is this sort of collision detection done in games? (I'm okay with recreating wheels, as a learning experience.) Examples?

I'm also intrigued about the possibilities for designing games or controls over hundreds of independently threaded objects, and am wondering if there are other games to look at as models. I don't know. It just seemed kind of cool and I wanted to show it off and see what others thought.  Smiley

"It's after the end of the world! Don't you know that yet?"
Offline StumpyStrust
« Reply #1 - Posted 2012-03-09 04:48:36 »

576 threads? that just sounds bad. From what I understand, one thread per core is best. 576 means lots of context switches which eats at performance.

Offline Roquen
« Reply #2 - Posted 2012-03-09 07:13:26 »

For actors you need to use pico-threads...not real OS threads.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline StumpyStrust
« Reply #3 - Posted 2012-03-09 08:11:44 »

very interesting...just looked up pico-threads and well....

Offline Roquen
« Reply #4 - Posted 2012-03-09 08:38:07 »

Better yet look at one or both of these frameworks:

http://www.malhar.net/sriram/kilim/
http://akka.io/

For real threads: I use the rough rule of thumb that I want somewhere between 1.5-2.5 logically active threads per core.   By logically active I mean that within some time window that number threads are attempting to run.  If you only have one per core, then if it gets stalled then the scheduler has nothing to do and that core sits idle until the stall is resolved.
Offline theagentd
« Reply #5 - Posted 2012-03-09 08:49:33 »

Better yet look at one or both of these frameworks:

http://www.malhar.net/sriram/kilim/
http://akka.io/

For real threads: I use the rough rule of thumb that I want somewhere between 1.5-2.5 logically active threads per core.   By logically active I mean that within some time window that number threads are attempting to run.  If you only have one per core, then if it gets stalled then the scheduler has nothing to do and that core sits idle until the stall is resolved.
Hyperthreading improves this even further. It's a myth that hyperthreading doesn't help games at all, since properly multithreaded games can sometime benefit more from Hyperthreading than from additional cores in memory bottlenecked situations. This is true for my multithreaded CPU particle simulation as well as for DICE's newer Battlefield games.

As Roquen said, it's better to have more than one thread per core, and I can squeeze slightly more performance out of my particle simulation if I set it to 8 threads instead of 4 (I have a dual core CPU with HT, so 4 logical cores).

Myomyomyo.
Offline philfrei
« Reply #6 - Posted 2012-03-09 19:53:49 »

...This is true for my multithreaded CPU particle simulation as well as for DICE's newer Battlefield games.

I'd be interested in seeing the links, @theagentd!

Thanks to all for the various references.

I have to admit, while the discussion about optimum threads per core has its benefits, I'm not particularly interested at this stage. I'm embarking on learning about how to effectively use "Actors" or other concurrency-related patterns, and am more interested in what might be derived from them. Things like particle-systems, or molecules glomming together or splitting, or ant/bee colonies, or crystallization modelling--these are some of the things that come to mind. And I wonder about how some of this might be put to game use. Maybe that will lead to something fresh and new, as opposed to remaking [fill in the blank].

Having hundreds more threads than cores is not going to be optimal, but neither is a single game loop thread. It seems interesting to me to get out from under the "tyranny" of game loops, and look at other possible forms of organization.  Smiley

Running AI opponents seems like another fruitful avenue to explore. I'm just exploring.

Having independent threads seems to demand having a "different" sort of basis for collision detection. Traditional 'all-at-once" use of bins/quadtrees/etc. doesn't seem as effective. Am I wrong? I'd love to hear about it.

"It's after the end of the world! Don't you know that yet?"
Offline sproingie

JGO Kernel


Medals: 202



« Reply #7 - Posted 2012-03-09 21:32:00 »

Actors communicate by exchanging messages with each other in a system where each Actor has its own private message queue.  If Thread A talking to thread B will erase the message of thread C talking to thread D, then it's not an actor system.  It would be interesting to see how well Akka STM would scale up for the shared map though.

As for actor performance vs "omniscient" spatial tree algorithms, I suspect the tree is going to win every time.  It's a wonderful organizational tool, but there's always going to be a lot more overhead than an algorithm that understands the entire system at once.  This isn't to say you couldn't take a hybrid approach, however and use both.


Offline theagentd
« Reply #8 - Posted 2012-03-10 11:21:09 »

http://www.java-gaming.org/topics/particle-optimization/25566/view.html
That's more about particle stuff, but it does contain some screenshots and lots of info... xd

Thread to thread communication is inherently expensive, so it's a very bad idea to have lots of it, ESPECIALLY if the amount of synchronization increases with the amount of processing needed. Having one synchronization per object is an incredibly bad idea, since as the number of objects increases parallelism decreases, which is the exact opposite of what it should be. I've found that the simplest way of doing things is to split up the game into individual tasks. With some dependency information you can easily find out which tasks can be run in parallel to each other and simply run things that don't affect each other on different threads. This all sounds easier than it is of course. It's very easy to end up with one huge task and a few small tasks, which obviously runs single-threaded 99% of the time. Due to this it's therefore a good idea to split up large tasks into smaller independent tasks. This sounds harder than it is, but the thing is that large tasks are usually large because they do the same procedure repeatedly on several objects, for example updating objects, updating particles, e.t.c. These tasks are VERY easy to split up as long as you make the update functions order-independent and thread safe, but this is how it should be in the first place! It doesn't matter which particle I move first since they only collide with static geometry. For more advanced things like collision you can split it up into two passes. The first pass checks for collisions between objects and calculates a force to apply to the object. The second pass applies this force to each object. Both passes can be split up into smaller tasks.

For the game I'm making now (an RTS) I've prepared everything for multithreading. The heaviest parts of my game are visibility testing (a ridiculous amount of 2D ray-casting) and collision detection / "physics". Visibility testing just queries a grid for the objects in the vicinity of the unit and ray-casts to them to check for obstacles, and then adds the unit to a list of visible objects from the perspective of that specific unit. This can be done independent of the order of testing, and is inherently thread safe since it doesn't write to any shared resources. It's therefore extremely simple to just update every other unit in 2 or more threads.

Physics is a lot more tricky to get working, but my game only has very simple physics, so that helps a bit. In the first pass I query the immediate vicinity of each unit for other objects and then check for collisions with these objects. If a collision is found a force is calculated and added to the total force that will be applied to the unit. Note that the force isn't actually applied to the unit yet. This is done in a second pass, where the force is applied and then the unit is updated based on velocity. I then needed a third pass to update the grid with the new unit positions. This was actually done single-threaded since the order of units per grid tile needs to be deterministic, but I try to keep all threads busy with other tasks during this pass, which also happens to be very fast (something like 1000 variable comparisons with something like 1% actually needing to be updated).

In the end I made a small library for this kind of parallelism. It can be found here: http://www.java-gaming.org/topics/small-java-threading-library/25143/view.html If you have any questions about it just ask! =S

Myomyomyo.
Offline DrZoidberg

Senior Duke


Medals: 15



« Reply #9 - Posted 2012-03-13 00:26:33 »

An actor system is actually similar to a game loop with a few differences. The actors are automatically moved to one of several worker threads. Actors are always designed to be completely thread safe. So they don't modify any global state. And they don't modify the state of other actors directly. This is also called "side effect free". If all your methods are side effect free, then your code is automatically thread safe and that allows the actor scheduler to move your actors to whatever thread it wants. You could look into functional programming to learn more about side effect free multithreading. Functional programming and actors go well together.
http://akka.io/docs/akka/snapshot/index.html
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline philfrei
« Reply #10 - Posted 2012-03-13 22:01:31 »

@DrZoidberg - AKKA looks very interesting. Thanks for the link to the documentation. This link might work better than the one posted in the email above which failed for me:
http://doc.akka.io/docs/akka/snapshot/

I am working to make the individual threads "thread-safe". Interesting, when trying to add things like "bouncing" or "temperature". I have clumsy implementations of each now. Maybe will make a "beehive" and "flower bed" and a couple "nose holes" to check the smell of each based on Actor state. Also want to try a "fireflies" version, and eventually work out a way for them to sense each other and get into synch.

Mostly, though, this is to kind of make it real--reading about concurrency is really difficult in the abstract. I really have to have a hands-on project in order to understand Doug Lea's or Brian Goetz's books.

A bunch of Actors messaging into a "Disruptor" is another idea I'm thinking of trying to understand better, too, rather than contending (using synchronized) for the array that maps to the display area.

"It's after the end of the world! Don't you know that yet?"
Offline ra4king

JGO Kernel


Medals: 350
Projects: 3
Exp: 5 years


I'm the King!


« Reply #11 - Posted 2012-03-13 22:38:52 »

I can squeeze slightly more performance out of my particle simulation if I set it to 8 threads instead of 4 (I have a dual core CPU with HT, so 4 logical cores).
I can confirm this here as well, I've got an i7 2600k (hyperthreaded quadcore) and your multi-threaded particle test ran much faster with 8 threads rather than 4. It even ran faster with 16 threads! Smiley

Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (41 views)
2014-10-17 03:59:02

Norakomi (33 views)
2014-10-16 15:22:06

Norakomi (26 views)
2014-10-16 15:20:20

lcass (30 views)
2014-10-15 16:18:58

TehJavaDev (59 views)
2014-10-14 00:39:48

TehJavaDev (60 views)
2014-10-14 00:35:47

TehJavaDev (50 views)
2014-10-14 00:32:37

BurntPizza (66 views)
2014-10-11 23:24:42

BurntPizza (38 views)
2014-10-11 23:10:45

BurntPizza (80 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!