Like I said in my last post, I don't think is going to be a large project at all, but I hope I'm wrong.
So far, it has been as I predicted, the coding took me about 2-3 hours or so of actual coding and testing. I spent more time drinking water and talking to a friend online while I did the code then I actually coded, but it is done.
Cluster Basic is, well, basic. It avoids no obstacles, has no graph/grid structure it needs to index into because it has no obstacles, and it's easy enough to understand. The corner state of the box is there to be used, but isn't really used by the Cluster code. Because the Cluster doesn't actually care too much about where it's putting the members at. Because to it, the members are just a number stored in population that it checks against to make sure it has enough force to push with. You do need 2 members to push the box at all, even if 1 could do it by himself by force alone, in order to push in a horizontal or vertical line you require two members.
I'm going to type up a draft of a paper to accompany this project, and get it to the point where it adequately describes Cluster Basic, and put down all my ideas before I start working on Cluster with Obstacles.
Sunday, May 8, 2011
Friday, May 6, 2011
New Project: Cluster
Alright, Cluser isn't a very good name so far, but I'll think of a better one. Anyway, the point is to have an object B (that is a box), and a goal point G, and a Cluster C of small workers that move the Box to the Goal by working together to rotate and push the box.
I've just started working on it, even though I did start working on something like it before, although I won't go into detail on it. Anyway, there are a few things I know I'm already going to do.
The box's state can be represented by an array that holds it's position and the amount of movement the box will move next step of the simulation, as well as the mass of the box. Also, if I want, I can create a boolean table that will tell whether a given part of the box is being pushed or not, this can be used by C to determine where to place it's members in order to push it. Makes sense?
Also, the Cluster will determine how to move the box based on the manhatten distance between it and the goal. So most of the time I expect the Box to be moving diagonally toward the goal. I'll create this project without obstacles first, but once I add in obstacles I'll probably move from an array to represent the space that C,B, and G live in to some type of Graph, and then I can start applying path finding algorithms (specfically Dijkstras A* algorithm) to the search space. Either that, or come up with my own way of dealing with it. (Minding that if I did want to use Graphs, obstacles would be nodes with HUGE weights/cost to traverse)
Alright, I've got the main ideas written in my notebook, and next I'll start coding up the classes and functions. I don't think this is going to be a very large project at all. Hopefully I'm wrong!
I've just started working on it, even though I did start working on something like it before, although I won't go into detail on it. Anyway, there are a few things I know I'm already going to do.
The box's state can be represented by an array that holds it's position and the amount of movement the box will move next step of the simulation, as well as the mass of the box. Also, if I want, I can create a boolean table that will tell whether a given part of the box is being pushed or not, this can be used by C to determine where to place it's members in order to push it. Makes sense?
Also, the Cluster will determine how to move the box based on the manhatten distance between it and the goal. So most of the time I expect the Box to be moving diagonally toward the goal. I'll create this project without obstacles first, but once I add in obstacles I'll probably move from an array to represent the space that C,B, and G live in to some type of Graph, and then I can start applying path finding algorithms (specfically Dijkstras A* algorithm) to the search space. Either that, or come up with my own way of dealing with it. (Minding that if I did want to use Graphs, obstacles would be nodes with HUGE weights/cost to traverse)
Alright, I've got the main ideas written in my notebook, and next I'll start coding up the classes and functions. I don't think this is going to be a very large project at all. Hopefully I'm wrong!
Thursday, May 5, 2011
Runtime Analysis On Turret3D
Since I have yet to decide on another project, I decided to do some runtime analysis on my program. At first, I looked at just the complexity of the overall algorithm, and figured it to be O(n) where n is the max lookahead value for the targeting algorithm, but since that literally took 2 seconds of thinking to do, I decided to figure out the more specific runtime, so I started checking on the complexity of the mathematical operations used within my code. To save myself the effort of typing it all up, and because blogger doesn't support latex embedded math typescripting (I believe), here's a screenshot of part of my paper that I wrote up.
If you do the math, the numbers won't add up quite correctly, the reason for the addition complexity in the actual runtime (the first line in the picture) is because of the boolean checks used to test if the loop should terminate or not.
The runtime is dominated by it's multiplications, as well as it's loop of course. So instead of just O(n) it's O(n * multiplications * trig). But, the addition and boolean constant time operations are negligible really, but they're included for specificity's sake.
I really want to create something involving AI, or using some Genetic Algorithms. But I have yet to figure out exactly what I want to do
If you do the math, the numbers won't add up quite correctly, the reason for the addition complexity in the actual runtime (the first line in the picture) is because of the boolean checks used to test if the loop should terminate or not.
The runtime is dominated by it's multiplications, as well as it's loop of course. So instead of just O(n) it's O(n * multiplications * trig). But, the addition and boolean constant time operations are negligible really, but they're included for specificity's sake.
I really want to create something involving AI, or using some Genetic Algorithms. But I have yet to figure out exactly what I want to do
Subscribe to:
Posts (Atom)