Quantcast

Maximum PC

It is currently Fri Jul 25, 2014 3:19 am

All times are UTC - 8 hours




Post new topic Reply to topic  [ 30 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Updated: HEY! All you Wanna-be Game Programmers!
PostPosted: Tue Mar 20, 2007 11:15 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
I am working (with two other guys) on developing a RTS style game for our senior design project. If you have questions, feel free to post them here. I think it would be a great discussion. I plan on setting up a blog/wiki or something where I can write some articles about our experiences.

Just a little info for you:
2.5D (think starcraft-ish looks/graphics)
SimpleMedia Direct Layer (Great set of libraries, VERY open to cross platform work)
Development is in MS.NET 2.0 (C#)
A* for pathfinding
Maybe some networkin discussion (we are using a p2p schema)

Lots of interesting stuff....

----------- UPDATE ---------------
I know I have been busy, and I haven't updated, but here is some stuff for you all! A video of our oral presentation, our final report, and the power point from that presentation.

http://www.battlescape.net/Content/pres ... tation.avi
http://www.battlescape.net/Content/pres ... tation.ppt
http://www.battlescape.net/Content/pres ... Report.pdf


Last edited by CrashTECH on Wed May 30, 2007 7:38 am, edited 1 time in total.

Top
  Profile  
 
 Post subject:
PostPosted: Tue Mar 20, 2007 11:52 am 
Java Junkie
Java Junkie
User avatar

Joined: Mon Jun 14, 2004 10:23 am
Posts: 24222
Location: Granite Heaven
Sounds like a great idea, CT .. keep us posted. :)


Top
  Profile  
 
 Post subject:
PostPosted: Tue Mar 20, 2007 12:52 pm 
Million Club - 5 Plus*
Million Club - 5 Plus*
User avatar

Joined: Sun Sep 12, 2004 6:37 pm
Posts: 4745
Location: In the monkey's litterbox
This ought to be neat to see come together. I like RTS games and .NET, so this is interesting to me.

Any plans to post the code when it's done?


Top
  Profile  
 
 Post subject:
PostPosted: Tue Mar 20, 2007 2:37 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Oh for sure! I will run it by the other guys and see if they mind me passing out the Subversion info. You can openly download, but you can't commit without a password, so they shouldn't mind. It is a school project, and I think the way it works is we can't market it, so it isn't like we could make money from it.

I am sure there are lots of different things we could do better.

I might post the SVN info anyway, maybe we can get some helpful hints :)

Unfortunately, one of the Guys doesn't comment well, and he is known for his voodoo programming!


Top
  Profile  
 
 Post subject:
PostPosted: Thu Mar 29, 2007 8:13 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Sorry for no updates, we were having some crazy issues with the threads not locking correctly, and the peers were not connecting correctly.

Just to give you an idea of the size of the project to date:
Total Lines: 44335
Source Lines: 32301
Comment Lines: 12034

Anyway, I guess I will start off by throwing out how we handled A* and path finding a little bit (I won't explain A* as I don't think I understand it enough to explain, but I will provide some links later). One of the guys in the group found an A* library that came with a demo program, and it worked (or seemed to work) really well. We also created a "passable" file, which has the same height and width (in characters) as the map has grids. (So if the map is 500 grids by 500 grids, the passable file has 500 cols and 500 rows) This was filled with 1s and 0s to mark the grids that a Unit can pass on.

To handle flying vs ground based units, we created a series of "Layers". One for ground units, one for air units, and another for "weapon fire" (might not be able to climb a hill, but you can certainly shoot a missile up it!)

Now, the passable map is applied to the ground layer only, as the other two are free ranged. We decided to keep the weapon fire separate from the air units just for clarity's sake, and to make it easier to get collections of units by their layer.

Was it the best way? I don't know. Are there better ways? I am sure there are. However, it seems to work fairly well, and aside from the units motion being semi-fluid (depending on how they get from one grid to the next, they might turn and face a different direction rather than just follow the line) it works for what we are trying to do.

When a unit moves, it "reserves" the grid it is trying to move to, this is just an easy way to make sure two units do not fight for the same space. Also, if a unit, or group of units gets into what was a clear path before, the moving unit issues a new A* request to get a new path.


Top
  Profile  
 
 Post subject: Re: Hey! All you wanna-be game programmers!
PostPosted: Sun Apr 01, 2007 10:54 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Regarding A*, you need to make sure that you're using an 'admissable heuristic' in order for it to work correctly. I imagine the library has done the work for you, but in case it doesn't, this will be the line of sight distance between way points on your map.

CrashTECH wrote:
When a unit moves, it "reserves" the grid it is trying to move to, this is just an easy way to make sure two units do not fight for the same space. Also, if a unit, or group of units gets into what was a clear path before, the moving unit issues a new A* request to get a new path.

If two units have a path conflict and they're heading toward the same destination, is there an easy way to have one unit simply follow the path of the lead unit? That would save a lot of path finding calculations when large numbers of units get bunch together.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 02, 2007 3:56 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
I think the library took care of that, I didn't look at that portion of the project.

That is an interesting idea. I am not sure how we could pull it off though. I think it would require knowing what units were moving to what location, and then the surrounding locations? It might be something that could be implemented in a "group move" command or something of that nature I would think.

The A* calls are stupid fast though, and as it is written, units walk around each other.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 02, 2007 4:09 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
That is an interesting idea. I am not sure how we could pull it off though. I think it would require knowing what units were moving to what location, and then the surrounding locations? It might be something that could be implemented in a "group move" command or something of that nature I would think.

I like the 'group move' idea. A group of soldiers are probably going to move in some kind of formation (assuming no constrictions in their path), while a group of peasants are going to move in a mob.

I was thinking purely in terms of eliminating unnecessary path finding calculations. Typically you'll select say a dozen units in one area and tell them to go somewhere else. It doesn't make a lot of sense to compute the entire path a dozen times (not counting recomputing it due to conflicts) when all of the units are going to the same location. The library may use memoization to eliminate the extra calculations (which would be a pretty novel use of memoization -- I haven't seen it used with path finding before... but why not?).


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 02, 2007 4:31 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Gadget wrote:
The library may use memoization to eliminate the extra calculations (which would be a pretty novel use of memoization -- I haven't seen it used with path finding before... but why not?).


Can you elaborate?


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 02, 2007 10:51 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
Gadget wrote:
The library may use memoization to eliminate the extra calculations (which would be a pretty novel use of memoization -- I haven't seen it used with path finding before... but why not?).


Can you elaborate?

Memoization is just having the computer remember the results of recursive calls and then checking before (re)computing a value. For example, if we had a recursive routine for computing fibinocci numbers, a call of fib(10) will generate calls to fib(8) and fib(9) and fib(8) will call fib(6) and fib(7), and so on. If you draw the fib calls as a tree, you'll see that there is a lot of repeated calls to fib. Memoization simply stores the result in a table and if we've already made a call to fib(6), for example, just insert the value from the table.

In the case of your program, I'm wondering if the library is doing the same thing for the path finding.


Top
  Profile  
 
 Post subject:
PostPosted: Tue Apr 03, 2007 7:38 am 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
I will check on that. It would make a boat ton of sense to do that, but might be more difficult to store everything as I think there would be a lot more variations. I will see what the other guys say as I didn't implement the A* stuff.


Top
  Profile  
 
 Post subject:
PostPosted: Tue Apr 03, 2007 1:11 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Slightly different topic than above... It has to do with a custom structure that we are using to track unit locations, and making finding close units extremely easy...

Basically, we have a list of our Entities (we have a class structure with inheritance for different times of Entities, units, buildings, resources, etc) and they are added by reference to the list. This "array" holds references to the units and not copies of them.

We are sorting this list initially, and then periodically by the units X positions and then by the Y positions using a quicksort. Here is the code for the sorting:

Code:
public void SortList()
{
   QuickSortX(this.m_EntityList, 0, this.m_TotalItems);
   QuickSortY(this.m_EntityList, 0, this.m_TotalItems);
}

#region Quick Sort (Sorting array A[size])
private void QuickSortX(WorldEntity[] m_EntityList, int first, int last)
{
   int middle;

   //As long as the first position is less than the last,
   // continue sorting with recursive calls
   if (first < last)
   {
      //Partition the array and return pivot point
      middle = partitionX(m_EntityList, first, last);
      QuickSortX(m_EntityList, first, middle - 1);
      QuickSortX(m_EntityList, middle + 1, last);
   }
}

private void QuickSortY(WorldEntity[] m_EntityList, int first, int last)
{
   int middle;

   //As long as the first position is less than the last,
   // continue sorting with recursive calls
   if (first < last)
   {
      //Partition the array and return pivot point
      middle = partitionY(m_EntityList, first, last);
      QuickSortY(m_EntityList, first, middle - 1);
      QuickSortY(m_EntityList, middle + 1, last);
   }
}

private int partitionX(WorldEntity[] m_EntityList, int first, int last)
{
   int middle, i, j;

   middle = m_EntityList[last].X;
   i = first - 1;

   //Go through the array
   for (j = first; j < last; j++)
   {
      //Swap the current value if it is less than the choosen pivot value
      //So it is in the lower part of the array (below the pivot).
      if (m_EntityList[j].X <= middle)
      {
         i++;
         swap(ref this.m_EntityList, i, j);
      }
   }
   swap(ref this.m_EntityList, (i + 1), last);
   return i + 1;
}

private int partitionY(WorldEntity[] m_EntityList, int first, int last)
{
   int middle, i, j;

   middle = m_EntityList[last].Y;
   i = first - 1;

   //Go through the array
   for (j = first; j < last; j++)
   {
      //Swap the current value if it is less than the choosen pivot value
      //So it is in the lower part of the array (below the pivot).
      if (m_EntityList[j].Y <= middle)
      {
         i++;
         swap(ref this.m_EntityList, i, j);
      }
   }
   swap(ref this.m_EntityList,  (i + 1), last);
   return i + 1;
}

public static void swap(ref WorldEntity[] m_EntityList, int a, int b)
{
   WorldEntity oTemp = m_EntityList[a];
   m_EntityList[a] = m_EntityList[b];
   m_EntityList[b] = oTemp;

   // Update Units Index in the list
   m_EntityList[a].ProximityID = a;
   m_EntityList[b].ProximityID = b;
}
#endregion


The m_EntityList is an array that is a member of the class, holds the references as mentioned above. The WorldEntity is an abstract class, the parent of all of the Entity classes in the game.

I have a swap function written; and this is where the main issue comes in.

Code:
public static void swap(ref WorldEntity[] m_EntityList, int a, int b)
{
   WorldEntity oTemp = m_EntityList[a];
   m_EntityList[a] = m_EntityList[b];
   m_EntityList[b] = oTemp;

   // Update Units Index in the list
   m_EntityList[a].ProximityID = a;
   m_EntityList[b].ProximityID = b;
}


oTemp now contains the reference to the unit referenced in array position a. Position A, now has the reference to B. And then oTemp should be put into location B. Seems fair enough...

Does this mean, that now:
oTemp -> A -> B? Meaning that oTemp has the same reference as A, and then A gets the same reference point as B, so oTemp references B?

Or will this swap function actually change the references correctly so that we have A2 = B1 and B2 = A1?


Top
  Profile  
 
 Post subject:
PostPosted: Wed Apr 04, 2007 3:03 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Good post. There is a lot of meat in there, so I'm gonna break this up into two different replies.

CrashTECH wrote:
The m_EntityList is an array that is a member of the class, holds the references as mentioned above. The WorldEntity is an abstract class, the parent of all of the Entity classes in the game.

If it were me doing the design, I would rename WorldEntity to AbstractEntity. It is a fairly common naming convention to begin the name of abstract classes with abstract.

The swap function...
CrashTECH wrote:
I have a swap function written; and this is where the main issue comes in.

Code:
public static void swap(ref WorldEntity[] m_EntityList, int a, int b)
{
   WorldEntity oTemp = m_EntityList[a];
   m_EntityList[a] = m_EntityList[b];
   m_EntityList[b] = oTemp;

   // Update Units Index in the list
   m_EntityList[a].ProximityID = a;
   m_EntityList[b].ProximityID = b;
}


oTemp now contains the reference to the unit referenced in array position a. Position A, now has the reference to B. And then oTemp should be put into location B. Seems fair enough...

Does this mean, that now:
oTemp -> A -> B? Meaning that oTemp has the same reference as A, and then A gets the same reference point as B, so oTemp references B?

Or will this swap function actually change the references correctly so that we have A2 = B1 and B2 = A1?

Assuming you haven't overloaded the assignment operator, the swap code should work correctly, but your last two comments have me confused as to whether you understand how references work, or if you've just happened to choose a confusing notation. I kind of get the impression that your confusing how pointers and references work (which is easy to do!).

There is a single array of WorldEntity references A. You want to swap the WorldEntities in positions i and j. I'll use Ai and Aj to identify these objects in the psedo-code below (ie, the ith and jth elements in A). Remember, if these were pointers to the objects, then not only would the array literally be an array of memory addressess, but we would also have to explicitly dereference an element of the array in order to get at an object in it (eg *Ai). Because we're dealing with references, the language handles dereferencing for us and we can think of the array as containing the actual objects. In reality, swap is swapping memory addressess, which are typically ints. The psedu-code below suffices to swap two items in an array.

Code:
swap(Array A, int i, int j) {
  tmp = Ai
  Ai = Aj
  Aj = tmp
}


That was the easy part. I'm a little concerned that you decided to code up your own quick sort (especially for sorting non-primitive data), why your storing the array index inside of each entity object, and just what you're trying to achieve here. My hunch is that your sort of creating your own ad-hoc method instead of using better, well established, data structures.


Top
  Profile  
 
 Post subject:
PostPosted: Wed Apr 04, 2007 7:14 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Gadget wrote:
If it were me doing the design, I would rename WorldEntity to AbstractEntity. It is a fairly common naming convention to begin the name of abstract classes with abstract.

I am inclined to agree, however, I didn't write most of that portion of the code, and because a lot of other stuff that I didn't write was done this way, I am not going to rename it, and break things. Especially when they spent 6 hours or better yesterday, and got units to move, on two networked machines, fluidly! NICE!

Gadget wrote:
Assuming you haven't overloaded the assignment operator, the swap code should work correctly, but your last two comments have me confused as to whether you understand how references work, or if you've just happened to choose a confusing notation. I kind of get the impression that your confusing how pointers and references work (which is easy to do!).

I was pretty sure that what I had written was okay, but I started to question it when Steve (has done MOST of the programming, and I consider him to be a much better coder than myself) said it would do something goofy like that and end up with everything point towards B. I didn't want to agree, but Chad was tending to agree with Steve.

Gadget wrote:
That was the easy part. I'm a little concerned that you decided to code up your own quick sort (especially for sorting non-primitive data), why your storing the array index inside of each entity object, and just what you're trying to achieve here. My hunch is that your sort of creating your own ad-hoc method instead of using better, well established, data structures.

Well, I did it like this, only because we have two items we are sorting on. It is basically an array of WorldEntity class objects. Two of the properties of this class gives WorldEntity.X and .Y which represent the entity's x and y position (duh!) in pixels on the map. We sort first by the X and then by the Y to get everything in its appropriate proximity in the list.

If you have another idea, that would accomplish the same thing, and be quicker and easier to manage, please feel free to suggest! I had this quicksort coded from a data structures class, so it was just a matter of adapting it to sort on our x and y positions.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 09, 2007 3:03 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Assuming that this is the (partial) goal...
CrashTECH wrote:
Slightly different topic than above... It has to do with a custom structure that we are using to track unit locations, and making finding close units extremely easy...


If you haven't already, you might want to consider either an r-map or a quadtree. I'm still not 100% clear on your requirements above, but it sounds like this will be something that is tracking throughout the game, and not just done occasionally, right?

Typically, the most difficult part with a multi-dimensional nearest neighbor type problems is case when two units are close together but located near the edge of two different regions (depending on how you divide up your map). This might already be a known technique to game programmers, but from my limited computational geometry background, it looks like one possibly good method of eliminating/reducing this problem would be to select a set of points so that the edges of a voronoi diagram fall onto barriers that you cannot pass through like walls, mountains, streams, etc.

I think you may have just given me an idea for a paper. =)


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 09, 2007 3:44 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
Question: say two units are near each other in terms of x,y coordinates. Let's suppose that the units A and B are located at...

A: 1,1 B: 1:3

Let's also say that the 'world' is limited to the first quadrant, therefore, unit A is literally in a corner of the world (ie he can't go any further west or south). They're only two units of distance apart from each other, so they're close, right?

But what if there is a wall extending from 2,0 to 2,1000. In terms of x,y position, they're close, but in terms of physical closeness, they'd each have to walk ~1000 units of distance in order to touch each other.

Are A and B near each other?


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 09, 2007 4:21 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
This would be constantly tracked and updated. I am not sure our way is the best, and I am quite sure that it isn't, I just don't know anything that could work better (or rather, I haven't been able to think of one).

We have "grids" that are 50x50 pixels. We are tracking the units based on their pixel locations.

To determin if a unit is "close" to another, or in range, we check the distance between them (sqrt(X^2 + Y^2)) and if it is less than the distance they can see, they can see it. If it is less than their attack range, they can start attacking, otherwise, they need to "move" to be in range.

As long as maintaining our structure, this should be pretty quick and easy to see if anything is in range to attack it, or get a list of targets in range.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 09, 2007 4:23 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Gadget wrote:
But what if there is a wall extending from 2,0 to 2,1000. In terms of x,y position, they're close, but in terms of physical closeness, they'd each have to walk ~1000 units of distance in order to touch each other.


I (we?) don't know how to account for this, and more or less have kind of left that out of the maps we have made. We are coming down to three weeks left, and this thing I am working on is the last big chunk to finish. I would like to be able to account for that if I can though.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 09, 2007 5:02 pm 
Bitchin' Fast 3D Z8000*
Bitchin' Fast 3D Z8000*
User avatar

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
CrashTECH wrote:
This would be constantly tracked and updated. I am not sure our way is the best, and I am quite sure that it isn't, I just don't know anything that could work better (or rather, I haven't been able to think of one).


If you're going to use this grid based approach for determining if two units can attach each other, why do you need to sort the units by x and y coordinates? I guess when I saw that sorting routine, and figured that you were going to be tracking unit positions continuously throughout the game, I figured you were going to kill your machines by constantly sorting and resorting the units. This approach doesn't require any kind of sorting, which is good, mod is way faster than quick sort. =)

All you need to do is initially calculate every unit's grid location, and just update a unit's grid position whenever they cross a gridline. Of course, you also need to know what other unit's are located in a grid... the grid itself can be as simple as a two-dimensional array of lists. You just simply iterate through a unit's current grid and neighboring grids to determine which other units are in range. It doesn't address the x,y close but cannot attach each other issue, but I'm starting to think maybe it is best to treat these as two seperate problems anyways.

CrashTECH wrote:
To determin if a unit is "close" to another, or in range, we check the distance between them (sqrt(X^2 + Y^2)) and if it is less than the distance they can see, they can see it. If it is less than their attack range, they can start attacking, otherwise, they need to "move" to be in range.

I would suggest changing your range to be in equivalent units to X^2 + Y^2 and leaving the sqrt() call out of your distance calculation. Square root calculations are pretty expensive and easy to avoid in this case.


Top
  Profile  
 
 Post subject:
PostPosted: Mon Apr 09, 2007 5:12 pm 
SON OF A GUN
SON OF A GUN
User avatar

Joined: Mon Nov 01, 2004 5:41 am
Posts: 11605
Gadget wrote:
I would suggest changing your range to be in equivalent units to X^2 + Y^2 and leaving the sqrt() call out of your distance calculation. Square root calculations are pretty expensive and easy to avoid in this case.


Gadget wrote:
If you're going to use this grid based approach for determining if two units can attach each other, why do you need to sort the units by x and y coordinates? I guess when I saw that sorting routine, and figured that you were going to be tracking unit positions continuously throughout the game, I figured you were going to kill your machines by constantly sorting and resorting the units. This approach doesn't require any kind of sorting, which is good, mod is way faster than quick sort. =)

All you need to do is initially calculate every unit's grid location, and just update a unit's grid position whenever they cross a gridline. Of course, you also need to know what other unit's are located in a grid... the grid itself can be as simple as a two-dimensional array of lists. You just simply iterate through a unit's current grid and neighboring grids to determine which other units are in range. It doesn't address the x,y close but cannot attach each other issue, but I'm starting to think maybe it is best to treat these as two seperate problems anyways.


So, basically, you are saying that a linear search would be faster than some sort of managed structure? So we would have a list of all the possible grid locations, and then we can look at a specific range of grids and see what is there?

We were only planning on sorting the list after the "change" threshold reached a certain number. (Number of units added, or something) We would sort, and reset that count to zero.


Top
  Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 30 posts ]  Go to page 1, 2  Next

All times are UTC - 8 hours


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group