Advertisement Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

340 Neutral

About XXX_Andrew_XXX

  • Rank
  1. After four years of working on a PhD thesis in motion planning I can tell you that you're very very unlikely to find a drop-in implementation of ADA*. There are a few reasons why: - ADA* implies some degree of concurrency. That is, the planning 'Main' function of figure 5 runs in one thread, whilst your execution and sensing/obstacle code runs in other threads. A major question is then, 'how do I efficiently update my obstacle map, without using excessive memory and avoiding concurrency bugs?' - Like most planners described in academic publications, the focus is on describing a generic concept. A specific implementation will involve a selection of concrete data structures (priority queues, open lists, sets) that are potentially hand tweaked to be suitable for a given application. - Finally, the pseudo-code presented in the paper, coupled with the description of the algorithm is *the* reference implementation for this type of problem. Suck it up and write some code.
  2. XXX_Andrew_XXX

    Is there a built-in Python vector class?

    In almost all cases which make use of vector math, the array type in the numpy module is appropriate. All of the appropriate functions are implemented in optimized C, and the types are closely compatible with python lists. Some 'common' operations on numpy arrays that you would expect on a custom 2 or 3 dimensional vector class aren't present (dot product), but are very easy to reproduce.
  3. XXX_Andrew_XXX

    rebuilding a std::priority_queue

    The standard c++ heap API works on containers whose items support strict-weak ordering. The simplest implementation would be: struct VertexDistancePredicate { bool operator()(const Vertex* v0, const Vertex* v1) const { return v0->getDist() < v1->getDist(); } }; ... std::vector<Vertex*> q; VertexDistancePredicate pred; push_heap(q.begin(), q.end(),pred); pop_heap(q.begin(), q.end(),pred); make_heap(q.begin(),q.end(),pred);
  4. In the POSA book (Pattern-Oriented Software Architecture: Patterns for Concurrent and Networked Objects, Volume 2), the pattern is described as pipes and filters. However in this case, what you're describing is a C++ specific anti-pattern. I assume what you're looking for is flexibility in being able to design and assemble components in an arbitrary fashion at runtime. This type of architecture is attractive in situations where you need to be able to add numeric/scientific data transformations to a data set (eg. for image processing). The best example of this architecture is Microsoft's DirectShow. If you need flexibility at runtime, static typing may not be the best way to go. Although templates and MPL might allow you to produce a working system, they tend to be quite brittle from a design perspective - you still have to do a lot of work duplicating function signatures that you're over-riding. An alternative is to pass less strictly typed objects around your system, and add runtime tests to check whether data is in the correct format. boost::any is a neat way to do this. From experience, you're probably better off to look at a language which has better built in support for reflection and dynamic typing (Python/C#/Java/MATLAB). If performance in these languages is an issue, consider rewriting only the performance critical task bodies in C/C++. From a concurrency perspective, such architectures tend to scale poorly with respect to load balancing and resources. One thread per task isn't necessarily the best way to divide the problem into pieces, particularly if the arrangement of pipes and filters can change at runtime. For example, a single thread in the middle of the pipeline can have a severe impact on performance for the rest of the components (threads later in the queue are left with nothing to do), which effectively makes the problem serial. An alternative approach is to use a job queue and a thread pool with size dependent on available resources (number of cores).
  5. XXX_Andrew_XXX

    AI for an Air Hockey player

    The most basic school of thought is design a set of layered behaviors, which can be used as components in a state machine. At the lowest level there is are two competencies * setting a new trajectory for the puck (a path which includes time information) for the puck. * estimating future states of the puck At the middle layer you can add a number of basic air hockey defensive and attacking techniques * standard block * block off sidewall in the AI half (when you 'set' the puck to be slammed into the other half) * standard attack * sidewall attack in the opponent half (useful when the opponent comes forward). At the top layer you can use an state evaluation function (state machine) to select the technique which is most appropriate at the current time. An alternative to the state machine/layered behaviors is machine learning. Although these techniques might work, but it would probably be a bit of a stretch to get something like that going in a reasonable amount of (your) time. The basic concept is to try to maximize the probability of scoring goals, whilst minimizing the chance of the opponent scoring goals. The problem with even something as simple as air hockey is that the problem is large. The state space is quite large (velocities and positions for the two players and the puck), continuous and contains significant discontinuities (collisions) in some regions. The actions space is more reasonable (velocity of the ai), but is still continuous. As for specific ML techniques, anything which results in a function which maps states to inputs will result in *a* strategy, but controlling the level of difficulty of the ai is hard. Although something like NN might work, they're probably not worth the time you'll spend on training and debugging. AFAIK a 12D state-space is probably verging on being too difficult to solve with standard dynamic programming / reinforcement learning techniques. google keep-away soccer, a simplified robocup variant if you're interested in a hybrid behavior / reinforcement learning approach.
  6. XXX_Andrew_XXX

    Design a scientific data visualizer

    Check out matplotlib its a python library with similar functionality to MATLAB
  7. XXX_Andrew_XXX

    pthreads VS boost::thread

    Quote:Original post by fpsgamer The thing is that as I read the boost::thread documentation, the library feels slightly ... incomplete I've been lurking about following the boost threading code for the least the last five or six major boost releases. One of the old maintainers of the package (Bill Kempf) disappeared and not much happened for a while, consequently where most of the other boost packages have had major documentation upgrades, boost::thread hasn't (other than to docbook). The only really significant changes to the implementation to boost::thread has been related to thread-specific-storage, particularly with respect to making it function correctly regardless of the linking model used on windows. As for reliability, you really aren't going to find better threading code anywhere that will run (pretty much) anywhere with similar results. If simple threads and mutexes are all you need, sure, by all means roll your own. If however you need reliable cross platform support for doing practical synchronization (barriers, conditions, ...) that work and are *fair*, you'll struggle to implement them correctly, test them and validate to the same degree that the boost code is.
  8. XXX_Andrew_XXX

    Inverse Kinematics library

    The only open source IK library I know of is Peter Corke's (A very highly respected Australian Scientist/Researcher), MATLAB robotics toolbox. Given enough time it might be possible to convert this to native code, . IK can get pretty ugly, and it's nice if you don't have to worry about the intricacies of all of the math. In some cases there isn't one clearly defined 'optimal' solution to a problem. In such cases it might make more sense to explore alternatives which use forward simulation to produce many approximate solutions very quickly. James Kuffner ( has some great papers on using RRTs as an alternative to IK for controlling simulated humans.
  9. XXX_Andrew_XXX

    Field D* implementations or explanations

    Quote:Original post by mfawcett Does anyone know of any sample code implementing Field D*? Like most of the algorithms in this family A*/D*/D*-lite/LRTA* the implementation depends heavily on the type of data structure you are using to represent the grid/graph. I've implemented some of these algorithms in python and C++, and getting started was one of the hardest parts. 0. Make sure your underlying data structures are ready before you start implementing Field D* (your graph and priority queue structures should be really well tested). This may involve using grossly simplified data structures (sorted vectors instead of heap-queues and trivial adjacency list implementations of the graph), aim for correctness at the start rather than performance. 1. Start by implementing the simplest possible algorithm that works in a similar case (A*), you'll need it as a baseline to test other parts of your system. 2. Implement D*-lite, it is by far the easiest and best documented of this class of algorithms. From memory this involved a fair bit of fiddling around with my priority queue implementation. 3. Then try implementing field-D*. My implementations are based on maintaining a fixed length list of nodes, indexed by state. I tend to store the following in each 'node'. * the accumulated cost g * the cached heuristic h (only required if the heuristic calculation is expensive) * the backpointer bp (a performance improver, without a backpointer when you need to extract a solution you need to do a little more work). * an 'open' flag * a 'closed' flag A also provide a lookup function which takes a state and returns all of the states which can be reached (a list of the successors). As for the rest, I'm still going through the paper, I'll try to post more in a little while. Look at Dave Ferguson's website for a list of his papers, they are quite comprehensive. Quote:Original post by mrsmes i honestly don't know but you can go to google and type the question in there Sorry to rant, but you're a new member, if you can't directly answer a question in the AI forum, you really aren't qualified to make a statement like this. Just to make it very clear, these algorithms are non-trivial to implement, hard to debug and hard to ensure that they perform reasonably in a wide range of conditions. This forum has a large number of very intelligent readers whose comments I would like to hear, as I'm sure the OP would.
  10. XXX_Andrew_XXX

    Memory Managers and DLmalloc

    There are multiple possible new/delete operators that it is possible to overload, so it largely depends on what you're trying to do. You might want to have a look for information on placement new. Other alternatives may include overloading new/delete for a given class. See the Tips and precautions section of this article: , it has an example of a nice looking way to use placement new.
  11. XXX_Andrew_XXX

    Memory Managers and DLmalloc

    Static buffers work well in some specific cases, but there are a few key problems. One of the big wins for static buffers is for large number of (generally small) fixed size objects. Other optimizations can be achieved using a static buffer if you know that a certain subset of objects have a common (short) lifetime, in game programming a single frame is common. At the end of the frame a pointer into the static allocation buffer is simply reset. This approach is only feasible if the number of temporaries is small. In cases where the objects you allocate aren't a fixed size you can end up with 'gaps' in the statically allocated buffer after you free memory. This problem is known as fragmentation. Another big problem for custom memory allocators relates to ensuring thread safety without introducing significant overheads. Have a look at the HeapLayers project for a good examples of the different types of allocators which are possible. The choice of 'how-to' use a custom allocator depends on what you're trying to do, again there are some good examples in heaplayers.
  12. You can add code tags to your post which will make things easier to read.
  13. XXX_Andrew_XXX

    Leg and Walking Kinematics

    The big question, like with any simulation or modeling relates to the accuracy you're trying to achieve. If you're looking to have a nice looking simulation the process you'll follow will be slightly different to what you'll want if you're doing the simulation in preparation for the construction of a real robot. As for a starting point, I think you're going to need to investigate collision detection and response. For collision detection tests on for the end of a leg vs. a plane you can probably get away with a dot product. As for responses, that depends on how you want to transfer linear and rotational forces & velocities back from the collision to the rest of the vehicle. * The robocup community have a large number of AIBO simulators which might be worth checking out. * If the accuracy of most of the physics side of things doesn't worry you, or you're in a hurry a rigid body physics engine like ODE might help. An alternative approach more suitable for animation would be to hand tune one or more gaits (leg movement sequences) for your robot and just replay each when appropriate.
  14. XXX_Andrew_XXX

    Controlling physically based aircraft.

    It's really important if you need help with a control type problem to give the model (or a reference to the model) that you're going to be using. Depending on how realistic you need the responses to be it's probably also mentioning what flight conditions you're operating through (velocities and angles of attack). If you get really stuck Timkin in the AI forum is a bit of a guru with this type of thing (he works on unmanned aircraft).
  15. XXX_Andrew_XXX

    Neural network for racing AI

    Quote:Original post by K_J_M A waypoint system which defines a best line for the ai cars to follow is usually suitable for most racing games. I think it's worth stressing that although in some cases waypoint systems are appropriate, that isn't always the case. If you use just a waypoint system you are implicitly relying on the fact that the vehicle controller can accurately track linear segments, and that the dynamics effects of switching between segments are negligible. For some vehicles this may be acceptable, and for others it might not. There are lots of examples where a level designer / artist could place either too few or too many waypoints without having a sufficiently good understanding of the underlying dynamics to predict what the results will be. Think about sharp 'S' bends and the results of under or over damped response tracking a linear segment. Waypoint based planning has it's merits, but there are alternative path representations (including splines), which may be more appropriate depending on dynamics and control.
  • Advertisement

Important Information

By using, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!