Thread: A Challenge in C++

  1. #1
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341

    A Challenge in C++

    I'm starting college in August and before I do, I want one more good challenge; something that combines the hardest parts of C++ programming with windows, DrectX and artificial intelligence. My idea is to create an Ant community(or any animal) where anyone could write a class with the artificial intelligence that would govern their ant's actions and compete with the other ants for survival. Each ant would be it's own thread and would have to communicate with the world class in order to move, look-around, build things, pick up objects, etc... Here's my problem: my knowledge of threads is, well, limited. And I know the C way of making threads. I don't know if C++ has a way, but if it does, I'd like this project to be entirely in C++, (vectors, classes, etc...) The main issue, for me would be communicating between threads, since the ants would only be able to "try" to move left. The would never have control over the laws of nature and simply change their coordinates. The world class would govern that as well as the animation.
    If anyone has a good reference on threads in C++, it would be appreciated. I will post any future questions about the C++ aspect of the project on this thread.
    Don't quote me on that... ...seriously

  2. #2
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    As far as I know, both C and C++ don't have built-in ways to do threads, because threading is platform specific.

    When you say the "C way", do you mean using pthreads? pthreads is a very commonly used threading library for Unix/Linux platforms. It can be used on Mac OS X as well since it is Unix-based.

    But anyway, so there is no standard C++ threading library, however....there are some options....

    The first option that comes to my mind is SDL. It is a multimedia library that is becoming popular among many, and it is multiplatform, and has its own multiplatform threading library with it. So you can use that.

    The Boost library is also very popular. I have actually never used it, although I really should...since I hear much of it is going to become part of the next standard...but I just did a quick search and I discovered that the Boost library also has a threading library with it. It is multiplatform, and you can use that as well if you want.

    http://www.boost.org
    http://www.libsdl.org
    My Website

    "Circular logic is good because it is."

  3. #3
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Quote Originally Posted by DavidP View Post
    As far as I know, both C and C++ don't have built-in ways to do threads, because threading is platform specific.

    When you say the "C way", do you mean using pthreads? pthreads is a very commonly used threading library for Unix/Linux platforms. It can be used on Mac OS X as well since it is Unix-based.

    But anyway, so there is no standard C++ threading library, however....there are some options....

    The first option that comes to my mind is SDL. It is a multimedia library that is becoming popular among many, and it is multiplatform, and has its own multiplatform threading library with it. So you can use that.

    The Boost library is also very popular. I have actually never used it, although I really should...since I hear much of it is going to become part of the next standard...but I just did a quick search and I discovered that the Boost library also has a threading library with it. It is multiplatform, and you can use that as well if you want.

    http://www.boost.org
    http://www.libsdl.org
    Correction: I know the "windows" way to make threads. I may just assume that my program will run on windows platform. But I'll check out boost.
    Don't quote me on that... ...seriously

  4. #4
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    Well the "Windows" way would be the same for both C and C++....unless you use something like Boost....but that is just going to access the Windows API in the background anyway.
    My Website

    "Circular logic is good because it is."

  5. #5
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Here's an example of the kind of threading I've done:
    Code:
    #include <iostream>
    #include <string>
    #include <windows.h>
    
    bool printing = false;
    void PrintingFunction(std::string s)
    {
    	int i;
    	for (i = 0; i < 100; i++)
    	{
    		while (printing);
    		printing = true;
    		std::cout << s << '\n';
    		printing = false;
    		Sleep(100);
    	}
    }
    unsigned long __stdcall ThreadFunction(void* data)
    {
    	PrintingFunction("Secondary Thread");
    	return (unsigned long)data;
    }
    
    int main()
    {
    	void* threadHandle;
    	unsigned long threadID;
    
    	threadHandle = CreateThread(NULL, 0, ThreadFunction, NULL, 0, &threadID);
    
    	PrintingFunction("Main Thread");
    
    	WaitForSingleObject(threadHandle, INFINITE);
    	CloseHandle(threadHandle);
    
    	return 0;
    }
    Is that acceptable, outdated, obsolete...?
    Don't quote me on that... ...seriously

  6. #6
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Ireland
    Posts
    8,446
    Boost::threads presents you with a near-portable threads mechanism, so interesting in fact that is part of a much larger discussion about threads support in later C++ standards. So I would always try and go that way. If for anything else, for the sneaky suspicion that whatever may come up next, it will in some way or another be similar to the interface provided in boost::threads.

    Another advantage (or not! depends on who's looking) is that it is indeed very easy to use. The documentation is easy to follow and you'll be "weaving threads" in no time. This of course has a price that I have payed my first trips over boost::threads. The price is this:

    You'll crash your app and extend your debugging times considerably over the first tries (months). Because no matter how good a threading framework is, for beginners on the subject like me or you, things like locks, mutexes and race conditions have very fine details that can't be all discussed in the course of a framework documentation, neither described by its interface. But I believe you'll get the hang of it soon enough.
    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  7. #7
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    Is that acceptable, outdated, obsolete...?
    You may want to read this article (and afterwards maybe some others) about
    CreateThread and _beginthreadex issues:

    http://www.microsoft.com/msj/1099/win32/win321099.aspx

    to decide what you should use
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  8. #8
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Quote Originally Posted by DavidP View Post
    When you say the "C way", do you mean using pthreads? pthreads is a very commonly used threading library for Unix/Linux platforms. It can be used on Mac OS X as well since it is Unix-based.
    Pthreads are also implemented for win32 and they work well there:

    http://sourceware.org/pthreads-win32/


    Brad0407:

    funny, I'm working on a very similar project with the main difference, that there are vehicles with scriptable behaviour (added to their own KI) instead of ants and I'm using a distributed architecture (there are to many vehicles to simulate so one machine can't handle it)

    for your ants your sure want to read about herd models/flocking. thats some (simple) algorithm to simulate very realistic herd behavior. define the same 3 or 4 rules to every herd member and get your herd behaviour
    http://en.wikipedia.org/wiki/Flocking_&#37;28behavior%29

    another thing: one thread per entity (ant in your case) is not the prefered approach in that kind of simulations for several reasons (mainly much finer control over the time is needed). Often a own scheduler is implemented that uses a queue for his processes and processes all of them at a defined simulation wide clock tick (windows multimedia timer is the reasonable thing to use on your os). the clock tick should be something about 16 ms to allow a reasonable image refresh rate. your open-gl image generator should also sit in the schedulers queue. on every run of the scheduler he reads the data and render every entity in the actual field of view.
    the scheduler himself spawns one (+ the number of cpu cores) thread that gets a process after the other from the queue and execute the run() method of that process. the run() method should be virtual so you can inherit different kinds of things. the run-method of the ants will have the herd-algorithm or some state machine holding the KI-methods and the image generator has the open-gl stuff in it's


    I hope what gives you some ideas. Would be nice if you update the status of your work here from time to time so we maybe can exchange experiences.
    Last edited by pheres; 07-08-2007 at 03:08 AM.

  9. #9
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    The first idea I had was just a class for each ant with a single public function that the governing class would call for every frame. The ant could ask for a particular input as the return value of the function and the governing class would send thart input next time it called the function. With this approach, the governing function can control the ants very extensively. It could go through a second of animation where the ant couldn't do anything because the governing function wouldn't call the ant's function. during the animation. Then of course death would simply be to never call the ant's function again. But what if an ant takes an hour to decide what to do? The other ants would need to have their functions' return values processed while this was going on. So I would need a thread to wait for each ant. Why not just make each ant it's own thread and put their requests for information/action in a queue that belongs to the governing class? That was my logic.
    Don't quote me on that... ...seriously

  10. #10
    Deathray Engineer MacGyver's Avatar
    Join Date
    Mar 2007
    Posts
    3,210
    Quote Originally Posted by Brad0407 View Post
    Why not just make each ant it's own thread and put their requests for information/action in a queue that belongs to the governing class? That was my logic.
    Probably because if you have lots of ants, you could end up starting too many threads.

    The Unreal Engine, while an FPS-based game engine, had the same thing to consider. The engine sets up a virtual machine where the language of choice is a Java-like language. Each object of class Actor appears to have its own thread, but in reality, it does not. All threading issues are handled by the virtual machine, and the programmer is oblivious to the inner workings of thread management. I read something somewhere that they simulate threads, which I imagine means the virtual machine has "threads" of their own, but they are not mapped one-to-one with native threads.

    A lot of the code is event-based, too, and a manager classes/objects are used frequently to pass events down the chain.

    This is probably way too in depth for a game of your type, but I figure it's worth mentioning.

  11. #11
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    The ants public behavior (callback) function of course must return in a time much smaller than the simulation tick duration, that must be assured by the behavior design. my run() methods for example just process a state machine: they look at the actual state, maybe ATTACK, execute all behavior routines forced in that state (update their position, fire and so on), check the values of all transitions from the actual state to other states and switch the state if one is true. then the method returns. so all data values are updated only one time per tick.

    your governing (or manager) class shouldn't decide when an ant dies. the ant should decide (or better their state machine transitions) and their state machine should switch to state DEATH if so.

    of course some global decisions have to be made too. therefore beside the state machine execution the execution method calls a function back in the manager class first. for example I calculate a global visibility / audibility map before the next tick (who is in sight of who) this way. with the one thread per ant method you'll have no defined update cycles. also you'll depend on the internal scheduler of the os and whats probably not what you want. the os scheduler does not run ant1 ant2 ant3 ant4 and so on. he runs ant1 for a while till he decides it's enough and runs antX when for next time. so every ant updates it states eventually much more then one time and then goes to sleep eventually in the mid of an running (state machine) update. shure you can work around this stuff by design, but the result will be not very simulation-like.
    Last edited by pheres; 07-08-2007 at 10:55 AM.

  12. #12
    Registered User
    Join Date
    Nov 2006
    Posts
    519
    Quote Originally Posted by MacGyver View Post
    A lot of the code is event-based, too, and a manager classes/objects are used frequently to pass events down the chain.
    exactly. thats what i've meant with "global decisions". in my example the pre-tick visibility update. the result of this creates events (expressed by transitions) for the behavior state machines. in my case a camourflaged vehicle reads the visibility map and gets some "position detected" event and switch to a state which is designed to react to that.

    I guess the core functionality of the virtual machine MacGyver talks about is an own scheduler.
    Last edited by pheres; 07-08-2007 at 10:56 AM.

  13. #13
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    >> Probably because if you have lots of ants, you could end up starting too many threads.
    My computer's running ~1000 threads right now and since I only plan to have 5 - 20 ants, I figured by program's number of threads would be an after thought. I'm not very experienced with high thread counts so I may be wrong. If I do decide to take the simulation farther, I'd see if I could use one of the college's systems with 128 4-core processors.
    Of course, if it's just bad programming practice, let me know and I'll find another way.

    >> A lot of the code is event-based, too, and a manager classes/objects are used frequently to pass events down the chain.
    The manager class will be event based where the ants (movement, interacting with objects) and time invervals (check for starvation, food spawn, etc..) initiate the events.

    >> your governing (or manager) class shouldn't decide when an ant dies
    The governing class is designed to act as nature and make sure that the ants obey its laws. I figured since an ant can't decide to just not die of starvation, it shouldn't be the ants choice.

    As a final note: I may be going overboard on threads. I've never written a program that had a decent reason for multi-threading, so I may be over-eager to use them. Oh, and I have basically no knowledge of proper uses of threads seeing as I learned all I know from about 10 pages of "Tricks of the Game Programming Gurus" by Andre LaMothe.
    Don't quote me on that... ...seriously

  14. #14
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Brad0407 View Post
    >> Probably because if you have lots of ants, you could end up starting too many threads.
    My computer's running ~1000 threads right now and since I only plan to have 5 - 20 ants, I figured by program's number of threads would be an after thought. I'm not very experienced with high thread counts so I may be wrong.
    The problem is that the world state has to be properly synchonized with what the ants are doing. There are two basic ways of designing it:

    1. Computation is divided into two serial operations. First, the ants all "think" and decide what their new states will be. Once ALL the ants have done this, then the world state is updated to reflect the changes in some consistent way. This requires very little locking during the "thinking" stage, provided the ants do not interact much with each other while they think. But the disadvantage is that all the ants must wait until the SLOWEST ant finishes thinking before any changes to the world state can be applied.

    2. Computation is an ongoing, concurrent process of ants thinking and updating the world state as they make decisions, each at its own rate. This requires a whole bunch of locking and resource notification to maintain consistent world state between all the updates the threads are doing. This is not only less efficient (than if you didn't need to lock), but much more difficult to code correctly.

    So you basically have to choose which method has advantages which outweigh the disadvantages. You might not be able to discover this a priori so you might as well just pick one approach, try it, and tell us how it goes.

  15. #15
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Quote Originally Posted by brewbuck View Post
    The problem is that the world state has to be properly synchonized with what the ants are doing. There are two basic ways of designing it:

    1. Computation is divided into two serial operations. First, the ants all "think" and decide what their new states will be. Once ALL the ants have done this, then the world state is updated to reflect the changes in some consistent way. This requires very little locking during the "thinking" stage, provided the ants do not interact much with each other while they think. But the disadvantage is that all the ants must wait until the SLOWEST ant finishes thinking before any changes to the world state can be applied.

    2. Computation is an ongoing, concurrent process of ants thinking and updating the world state as they make decisions, each at its own rate. This requires a whole bunch of locking and resource notification to maintain consistent world state between all the updates the threads are doing. This is not only less efficient (than if you didn't need to lock), but much more difficult to code correctly.

    So you basically have to choose which method has advantages which outweigh the disadvantages. You might not be able to discover this a priori so you might as well just pick one approach, try it, and tell us how it goes.
    I'm going to try numero 2. I'm going to have the central class govern the laws of nature. I'm also going to use it to keep the internal states of all the ants. All the ants will be able to think whenever they please, but only one will be allowed to change their state at a time because all state changes must be cleared through the central class. Does that sound like a good plan or not?
    Don't quote me on that... ...seriously

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. AI Challenge
    By unknown_111 in forum General AI Programming
    Replies: 0
    Last Post: 10-02-2007, 12:18 AM
  2. Programming Challenge (for my school)
    By Ezerhorden in forum C++ Programming
    Replies: 2
    Last Post: 01-04-2006, 06:56 AM
  3. Calc challenge
    By cerin in forum C++ Programming
    Replies: 5
    Last Post: 02-06-2005, 04:57 PM
  4. Challenge?
    By Mackology101 in forum C Programming
    Replies: 5
    Last Post: 11-23-2004, 02:30 PM
  5. Requesting a challenge
    By RealityFusion in forum C++ Programming
    Replies: 8
    Last Post: 08-18-2003, 08:24 PM