5
\$\begingroup\$

I'm working on a game sort of thing where users can write arbitrary code for individual agents, and I'm trying to decide the best way to divide up computation time.

The simplest option would be to give each agent a set amount of time and skip their turn if it elapses without an action being decided upon, but I would like people to be able to write their agents decision functions without having to think too much about how long its taking unless they really want to.

The two approaches I'm considering are giving each agent a set number of bytecode instructions (taking cost into account) each timestep, and making players deal with the consequences of the game state changing between blocks of computation (as with Battlecode) or giving each agent it's own thread and giving each thread equal time on the processor.

I'm about equally knowledgeable on both concurrency and bytecode stuff, which is to say not very, so I'm wondering which approach would be best. I have a clearer idea of how I'd structure things if I used bytecode, but less certainty about how to actually implement the analysis. I'm pretty sure I can work up a concurrency based system without much trouble, but I worry it will be messier with more overhead and will add unnecessary complexity to the project.

\$\endgroup\$
3
  • \$\begingroup\$ probably you are losing the main focus, in java you have the JVM that slow down every operation, look at minecraft and how inefficient it is, how you are supposed to optimize something in java? the best JVM for performance is probably the Dalvik that is a really small JVM with a fast GC, but optimizing this kind of things in java just doesn't make sense to me, if you want performance use C++ \$\endgroup\$
    – user827992
    Aug 14, 2012 at 15:52
  • 2
    \$\begingroup\$ It sounds like your agents are only reading world state and making decisions based upon it -- is that true? Do they ever write to or otherwise modify state? \$\endgroup\$
    – user1430
    Aug 14, 2012 at 15:53
  • \$\begingroup\$ I think you should force your users to be concerned about how long it takes to compute an action. If they are taking 100 seconds or more to "decide" on something, I would be concerned that maybe your players are not trying hard enough to come up with "fun" and quick solutions. I don't quite understand your use case, but I don't think you want to give each player all the time in the world to make a single decision. \$\endgroup\$
    – kurtzbot
    Sep 25, 2012 at 22:50

1 Answer 1

4
\$\begingroup\$

A casual analysis:

Why threads?

Simply running each user's code in a separate thread is easy. But two threads don't always get equal processor time.

The classic example is to start two threads, one of which prints A and the other B. You'll see ABABAB a lot, but eventually ABABBA happens, sometimes even ABBBA, sometimes even ABBBBA. Most operating systems provide no guarantee that threads get equal time in the short term.

Depending on the game though, a small short-term advantage may be negligible.

Why bytecode?

Bytecode restrictions get you closer to absolute fairness, as they are "closer to hardware", or as close as you'll likely want to get. Allowing only a certain number of bytecode instructions per tick from each entity is equivalent to implementing fair multithreading (except, of course, the loss of multi-core optimisations that the OS cannot do on custom "threads"). Battlecode allows 6000 bytecode instructions (of Java?) per tick.

Mojang's 0x10c (multiplayer, in development) emulates DCPU-16 architecture, which admittedly is a pretty ridiculous length to take this to. However, it is an example of going all the way to (at least virtual) hardware.

tl;dr

If short-term differences are important, study the possibility of bytecode. Else threads.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ +1. I would even go so far as to say, "80% of the time, optimise your single threaded code". In other words -- focus on the bytecode unless you have every reason to believe that even with nigh-faultless efficiency, you still won't have sufficient CPU time. \$\endgroup\$
    – Engineer
    Dec 6, 2012 at 21:52
  • 1
    \$\begingroup\$ I would go even further than @NickWiggill, and say "if you have to ask, then don't use threads." \$\endgroup\$ Dec 6, 2012 at 23:10

You must log in to answer this question.