Its been about a month since my last article and I've worked on a few different things which are all included in the source code provided here along with other relevant files available for you to download. The changes to the Mars Mission game itself are not immediately evident and though there are a few minor changes you'll have to put up with one more article about collision detection before things get really interesting. I wanted to progress further in the final project before writing a third article but since this collision-detection business has given me a bit of a hard-time and there's plenty to talk about I figured I'd just put it all out there and then move on. I have no quota or commision so we'll just wing what gets done whenever i get it done and write about what's what when that happens. As I've explained briefly in the first article of this series, the collision-detection scheme in the original version of this project was a game-killer because my ships would get stuck against the edges of the landscape and ruin everything. Part of the reason why this was such a problem was because there was no save-game feature which was sorely missing.
The game now includes the option to save/load. Hoorah! This was implemented using Xml by having every object class build its own xmlNode given a reference to the main xmlDocument. To do this they often had to call other object classes contained within them and starting with the Solar-Object calling its object-container and then its landscape which has to call its own object container for each cell and each cell may have a ship which may have an astronaut which may have resources... and so on. This was not altogether very difficult to do and the reverse is simply a call to the classes' static functions which generate objects given a reference to an xmlNode.
The game save/load feature will require that I keep up with the game as things go along or it will become a huge problem later if these future changes are not immediately reflected in the relevant save/load functions. its just a matter of referring back to them every time some new tidbit is implemented.
As promised action/resources are coming soon. Presently I've done a bit of work on developing the resources available in the game for the actions. The action/resources engine takes in input-resources and returns output-resources at their completion. You can load what I've got running by making a small change to the program.cs file where there are three projects to choose from all quietly biding their turn to shine upon request.
static void Main()
The code sampled above comments out the first two forms formMarsMission()(which you just have to uncomment if you want to run the game), the second is formXmlResourcesActionEditor() and the last is what we're here to talk about : formStructureInteriorEditor().
But before I talk to you about that. I should tell you about some of the new changes I've made to the game which you can explore right away. First of all. You start your life in a cave. No big deal, ok. you're right, you've seen this before. but there are a few new controls which might interest you. The ship-controls on the right of the screen have label-button controls for the dampers and engines which you can click to set either both (all four in the case of the fighter ship) damper controls simultaneously or individually, toggle these on and off which doesn't appear to be much improvement until you consider that you can do all this in the 'Ship-Details' form. Click the 'details' button on the ship-controls groupbox and a new form will appear. then when you select another astronaut piloting another ship (must select the ship's pilot to control the ship) then you can summon two ship-detail forms and control both ships using these mouse activated controls on the forms. its tough to do when you're trying to fly out of a cave without seeing the cave around you, i wouldn't recommend it. but on the landscape above the highest peaks its fairly easy to move the ship from here to there safely. just don't forget that your landing gear can be lowered or raised on this form as well.
forgive the fighter's dopey looking landing-gear, i'll get around to fixing this because it just looks kind of cheesy right now with those two over-sized legs sticking out. yea, yea, go ahead and laugh but the suspension's great!
Flying the fighter is considerably different than flying the shuttle. The fighter has four thrusters and these are not controlled by the mouse button as the mouse-button will be required for the fighter's primary cannons. Though you can still opt to control the ship's heading using the mouse position on the screen, toggling between this form of heading control and controlling the heading using the third blue hand on the CircleControl seen in the image above can be done using the context-menu(right-mouse click) on the main view screen. Since the fighter has auto-dampers you can fly it as if you were in zero-G regardless of the gravitational force outside the vessel and the ship will always appear with the nose up regardless of your heading so that you can turn left or right by positioning the mouse left or right of center screen. Then using the keys S, F, E & C to move left, right, up & down respectively you can slide about at will. Its a bit disorienting at first to see the planet's landscape spin around you but a bit of practise and you'll get the hang of it. Though the shuttle's controls give you both horizontal and vertical dampers the fighter vessel's got only the one which you can activate using the D key on your keyboard.
If you've downloaded and run the code from the 2nd article in this series then you won't have to rebuild all your images. The files your should put aside are : all the .rBmp files the the one .SOI mega-file. then paste these back into the same directory after you've extracted this new source code.
Newbie Game set-up help
For you newbies who know nothing about programming or C# you'll want to download Microsoft's C#2010. Then download the source-code file listed above and extract it somewhere on your hard-drive. Once you've done that you go into the directory that has the "properties" subdirectory and extract the three other files into that directory so that these files all appear listed below that same "Properties" directory you noticed before. When this is done you can run your brand new C#2010 computer programming language using the file-menu to load the Mars_mission.proj file and then press F5 and run the editor. to run the game you'll have to make a small change to one of the files. yes, you'll actually have to do some real programming. you can tell your friends you were 'writing code' and put it on your resume later, all you have to do is click the 'solutions' tab on the right. find the program.cs file listed there and double click it. Then add two right slashes '//' to the left of the line
and remove the right slashes at the front of a previous line
these right-slashes are code-characters that tell the compiler to ignore everything on the line that follows them so when you remove these from the start of a line you're 'un-commenting' the rest of the line which means that line of code will now be executed and when you add them to the beginning of another line you're 'commenting-out' that line of code which means it will be ignored. so, essentially you're saying "don't run that, run this" to the compiler.
when you're done press F5 again and the game Mars_Mission will begin execution. you'll want to read most of the article Mars Mission (2) before proceeding any further.
Polygon Collision Detection Scheme
The collision detection described here is quite flexible and needs little alteration to be ported to any other project you may want to use it for. I've tested it and it looks pretty good so if you want to use this you'll want to remove the formStructureEditor() to new digs on your own filing system and separate it from the rest of the MarsMission project. You can drop most of the classCollisionDetectionObject's variables as the only ones used by this collision detection system are dptPos (start position), dptEnd(end position), dblAngle(start angle), dblRotate(amount to rotate) and the instances of the classCollisionDetectionPolygon called cCDP.
I got rid of the astronaut's sprite during the debugging process. but you might like to note the rotation of the girl's arm relative to the rest of her body. That's because i didn't bother changing the code that controlled her arm rotation using the mouse wheel and it just locks to the body's rotation. It won't be like that in the end project but what this means for the world of sprites is something called a sprite-composite which i'm working on. What this is is a composite of sprites(as the name so apply implies) and a single call fetches an image of a collage of sprites as they should appear. These are put together in a way similar to how an individual sprite is produced one limb at a time and with a specific limb sequence except in the case of the sprite-composite its one sprite at a time, at whatever angle each sprite is supposed to be and in whatever configuration each sprite is at, each placed at a position relative to some 'master' sprite in a way similar to limbs. so your astronaut can be made of two legs a torso, a head and one arm with a separate sprite called 'arm' that does the GI-Joe kung-fu action thing. The arm sprite is positioned relative to its shoulder and anything you place in his hand is positioned relative to the hand ->relative to the shoulder->relative to the main body. since the spinning-thing in her hand needs to be drawn before the hand for it to appear inside the hand then there needs to be a specific draw sequence, such as, body, spin-thing-in-hand, and lastly, we draw the arm despite the fact that we needed to measure the arm's location before we knew where to place the hand-widget. and the whirligig spinning in his hand can have another thing jutting out and that would spin with its propeller winged jigamabob and the whole thing can be drawn with a single call to the sprite-composite its a part of. I'll use this later for the ships and their landing gear as well as a few other things. all this is built dynamically so the versatility is limitless. you plug'em together and they're ready to roll. its almost like plug'n-play.
So, another thing I've discovered recently is this 'animated-gif' thing. How long's that been around? forever, I guess. but since i only now bothered to look up from my own little world and found out there is such a thing you'll notice more of these in my articles in the future. and eventually, I'll get into the WPF groove but unfortunately that won't happen until I finish with this project. forgive me for being so slow to adopt new stuff its just going to take a while before i poke my head up again.
Notice, however, in the animated-gif above, the neat demonstration of what a polygonal collision detection system is. The project
formStructureInteriorEditor()has three modes:
- edit structure
- edit CDP (collision detection polygon)
- test move
The edit Structure mode is what I use to design the various rooms such as the inside of the ships themselves as well as the buildings like the Terran Base and any future buildings. Since these are closed Polygons with no entry/egress I'll have to implement a teleporter that will remove your astronaut character from one polygon and stick 'em in another, or the surface landscape, a cavescape scene or even a free-floating EVA mission in zero-gravity. For now, all we're going to do is look at this polygon detection system and the structure editor.
In the edit structure mode you can add/delete polygons from inside the room. What? you thought there would be just the polygon's perimeter and no wall's inside? Sure, what could be simpler? once we have one polygon together, they're all the same. but different. in any case, adding one or two or any number of polygons inside your main polygon's perimeter is easy as Pi, so easy its rad! (feel free to groan here). The structure itself is described on file as an array of arrays of cartesian coordinates. Where each array of cartesian coordinate constitutes a polygon and the zeroeth entry in the array of these polygons is the outer perimeter while all the others are obstructions contained inside it, though there are no tests to detect if any of the other polygons are in or out, this is left up to the interior-structure design engineer to figure out during the development phase. The structure-interiors can be loaded and saved, note that since these files are all contained within the same directory as the rest of the Mars_mission project it is advisable to continue using the the naming convention which I've used and loading/saving only xml files that start with the name "StructureInterior_".
The edit CDP mode works in a very similar manner but does not allow save/load features which I'll get around to when I actually include this into the game-proper. what it allows us to do, however, is add/remove points in the object in motion as well as move these around into whatever polygonal shape we want. The polygon collision detection algorithm fails at certain angles and positions if the Collision-Detection-Polygon (the thing moving around) is not convex in shape, but you can go ahead and give it a try anyway.
the CDP is defined as an array of radial points around a central position. This allows us to easily rotate the object in motion. Though this feature won't be necessary for the astronauts as they will appear in a 2-d side view and remain vertical, when we look at the catacombs and the Descent-like action game side of this project a triangular shaped rotating CDP will be just the thing.
Test-Move Mode : this is the mode you use to move the object around and see how it reacts when it tries to drive through a wall, or callously tries to rotate into some hapless polygon who was just minding its own business.
The context-menu will give you options appropriate for whatever mode you're in as well as let you change from one mode to the next.
Because I ran into so many problems in the development of this collision detection system I had to use a lot of on-the-fly debugging graphics tools which are currently commented-out but can be called-back to life relatively easily though doing so will seriously slow the system down to an aching crawl. the images this generates are stored on your harddrive at C:\\temp\\marsmission\\ and that's hard-coded everywhere there's a bitmap saving itself from obliteration so if that's a problem on your system you'll just have to figure it out. these debugging images are not necessary if you just want to test run the code. also for debugging purposes, the test-move mode keeps track of the locations of our poly-gone in motion object's as well as important stuff like angle and rotate and what-not at each frame of the test-run. you can review these by typing into the text-box that appears at the top left. up/down and pageUp/pageDown let you select the frame. since the frame count increases as you go along clicking 'up' or 'pageUp' won't stop the test-move animation from going about its business but a down will. you'll notice the output images reset themselves to whatever they were at that frame whenever you change the value in the text box and pressing the enter key will restart the animation from wherever you are. the problem with this is that even though i was able to stop and restart and reposition everything exactly the way it was one of my prototype
move() functions stepped back to a point before a bug and then proceeded forward again and failed to reproduce the bug. the damned thing just worked when it wanted to and then bugged again a few steps later. for that then, that
move() function has been put on notice and is sitting its ass out in the cold for its insubordination while its slower but more serious cousin does the job in a slow-but-stead sort of way. more on that below.
In the first article of this series we were looking at a circle as the collision detection object in motion. And there were a few complications involved there but geometry, trig and logic prevailed and that looks pretty good. Now I could have used the same functions as the ones in that article which are still used for the landscape's collisions, snip and paste here, cut and copy there, and we're done, right? but I ask you, What would be the fun in that? and so, here we are, a month gone past and no real progress or changes to the game itself but we do have something to talk about and the key word of the day is 'Polygon'.
A polygon, as I am sure you already know, is "a closed plane figure bounded by straight sides" and while we're here a convex-polygon is "a polygon such that no side extended cuts any other side or vertex; it can be cut by a straight line in at most two points". And so, given this definition and what you already know about polygons, certain things we took for granted in the case of a circular object in motion do not apply here. Namely, its not a perfect circle, which means we can't just measure a distance to the nearest edge from the center and decide whether or not that's a collision since the edges are odd-in-shape and the whole thing rotates such that all the sides can be anywhere at anytime. Therefore we have to consider the angle the body makes as it moves about, we also need to consider if rotating this object alone causes a collision before we test if moving it from A to B causes a collision. Ideally we would be doing these two tests as one move/rotate but this time around I've divided these two types of motion into two separate functions. First we spin then we move. Should I turn to a life of politics in the future I'll think about doing my moves before I spin but that's a different matter for another time.
First lets talk about what we're running into. Polygons yes, but it's easier to consider these as a series of lines instead so we break these polygons up into an array of lines which we keep in the
classStructureInterior objects I like to call
cSI's (Legal obligation stipulates that I must warn my readers that these cSIs have nothing to do with the popular forensics television program) that said, the
cSI has a two-dimensional array of type :
public class classStructureWallGridLineIndexArray
public int intLineIndex = new int;
public int intCornerIndex = new int;
Dividing the area which contains all the polygons inside the structure into neat squares of equal sizes the function
defineWallGrid() scans through each side of all the polygons and tests if any of these pass through the squares of this grid and each grid holds a list of lines that go through it. This will be handy later when we test if our polygon in motion collides with any walls by limiting our tests to relevant walls we pick off the grid and then keep track of which walls have been tested with a boolean array so as not to duplicate our work.
the animated gif below explains the relatively simple process of defining the grid:
As promised, we now look at the spin-collision function. This function further divides the collision-detection system in two more algorithms. The first of which tests if the trajectory of each point on our polygon-in-motion collides with a wall. The second part checks if the motion of an edge of this polygon crashes into a corner of the wall.
- polygon-corner -vs- wall-edge
- polygon-edge -vs- wall-corner
rotation : arc collision
To test whether or not the corner of our rotating polygon spins into a wall we measure a vector from the center of the polygon to the wall being tested. Then, using the radius of the point we're testing as the length of a right-angled triangle's hypotenuse and the distance to the wall we're testing as the adjacent side, we measure the angle of this triangle and add/subtract this angle to the angle of the vector to the nearest point on the wall, depending on whether the object is rotating in a positive or negative direction, and we then know at what angle any collision would occur. Testing this collision-angle against the start/stop angles of the rotating polygon's point we can then determine whether or not the rotation causes an arc-collision between one the polygon's points and a nearby wall. The animated gif below may give you a better idea as it describes what will happen if we rotate the polygon from its blue angle to the intended red angle.
here are a couple of debugging-graphics that I put aside for this article.
The "Case C" written at the top of these two last images indicates that its a case where the object is rotating counter-clockwise and the angles start/stop do not pass through zero radians. Case "D" rotates counter-clockwise and does go through zero, while cases A-B rotate in a clockwise direction. These debugging images were important for me to unmess my fuddled brain and you'll notice that neighter above case cause a collision while the one below does.
The next important step is to calculate how far beyond the wall our polygon's corner has protruded. Once we know this we try and see if moving the whole polygon over a distance equal to the vector from the offending point to the wall and see if this causes a 'static test', that is, if the rotated polygon is in a collision state if it moves in that direction. If it is then we measure how far we can rotate and call it quits for this corner/edge combination and move on but if it isn't then we move the polygon over to this new position and continue testing the rest of the corners and edges.
rotation : Edge collision
You may have noticed in the code that Pythagoras figures prominently. That guy was a genius. Here, looking at the edge collision test of a rotation we do much the same thing but since the edge is in motion and not the corner of the wall we have to change the rules a bit. First we test if turning the polygon creates a line/line collision between the polygon and the wall. Because its possible for the pointy tip of a triangle to rotate past a pointy tip of a corner we also do a "point is inside polygon" test by forming a polygon between all non-relevant points of our object and its start/stop positions of the corner we're testing then we ask 'is the corner of this wall inside our test polygon' before proceeding if either the line-test or the polygon-test tell us there is a collision or skipping ahead of they don't.
But trying to figure out how far the edge can go before it has to stop is not so simple because the edge is not at a constant angle and the two ends of this edge aren't necessarily the same distance away from the center so, though they may both have identical angular velocity relative to the center of the polygon their differences in radii means that the whole shebang's a bloop-bop, if you'll forgive my foul language. and so, what we need to do is look at this system as if the room were rotating around the object and the object was stationary. Once we do this then everything is simple again. or just about. let's just say 'simpler' and leave it at that.
First we calculate a vector from the center of the polygon to the nearest point on the start edge we're testing. Then using this distance as the adjacent side of a right-angle triangle and the distance from the center of the object to corner we're testing as the hypotenuse we do the pythagorean do-wop again and measure the difference between our result with the angle the corner makes with the center of the object. This difference is equal to the angle we can rotate our polygon before it hits this corner.
So we detect a collision then measure the distance to the corner by spinning the room around and we're done. see below.
Next we look at movement of the non-spinning variety. This should be easier and my first implementation turned out to the be the slow-but-stead reliable one which I plugged together in a couple of days, debugging and all. The previous version of this game had the nasty habit of sticking ships to walls making things difficult but the move() function described here makes one subtle change with solves this problem. Instead of doing a line by line test of the current position corners with the next position's corners this implementation decides which corners are facing the direction of motion then creates a polygon-of-motion out of what's important and neglects the stuff it leaves behind. This way, if you're ass is stuck it don't matter 'cos its neglected in the test when the front end is wider. You don't see it? have a look at the animated gif below.
what you're looking at is the process of building the array of points that constitute the motion-polygon we run through the
move_collision() function which tests this polygon against the walls to see if there's a collision. In the example above you can see what I mean by 'if your ass is stuck' . Looking at the example if you imagine that for some unknown reason the point #4 is found to be sticking into a wall by the minutest value such that testing a straight line between #4's old position and #4's new position would disallow the move and keep it stuck against the wall. By choosing to only look at the face of the moving polygon, given the direction of motion, we ignore the back-end of it and de-stickify ourselves with less pain that removing the cheap bandage you bought at the dollar-store last year after stepping out of the shower.
The process of building this polygon is fairly simple. We take the original unrotated polygon and turn it such that the direction of motion is at angle zero along the x-axis. Then with each point's cartesian value calculated we take the one nearest the top and the one farthest at the bottom and use these two as the extremes. Then we make an array of integers to keep track of the sequence of test points from top to bottom. Doing this I ran into a problem because i wasn't sure whether it needed to rotate clockwise or counter-clockwise until I decided that the polygon's base description must be clockwise so that the first radial coordinate in the array is the one with the smallest angle and the last radial coordinate is the one with the largest angle. with this rule in place and enforced with the function
OrderPolygon() in the class
classCollisionDetectionPolygon we don't need to worry and just proceed through each point from the one nearest the top, rotating clockwise until we reach the point nearest the bottom.
Armed with this sequence of points we then combine the start locations of each of these points on the polygon in motion and loop around in the reverse sequence through these same points along the edges of the polygon's end position.
you can see this in the function
classMath.classDoubleCartesian getMotionPolygon(ref classCollisionDetectionObject cCDO,
which is described in the animated-gif above.
The reason why this Move() function is not optimal is the way it positions the polygon after it detects a collision. The currently used implementation is less than ideal and I may or may not fix it as I just want to move along towards the action/strategy aspects of this game. But this is essentially what it does it moves the full distance and test if there's a collision. If there isn't it quits but if there is then it halves the last distance it moved and moves again in the opposite direction going forward/backward by halves until the distance it tries to move is so small it just quits and places the polygon in whatever the last position it was in that didn't cause a collision.
I can see my Software Engineering professor tsk-tsk-tsking and i hide my head with shame. but in my defense: it works.
since the only object I foresee not moving along tracks that guarantee there is no collision is going to be the player's ship i predict that this will do and i won't regret using the inferior but more reliable function.
the alternate Move() function which is also included in the source-code but is commented out works pretty good but it has the nasty habit of allowing a rotating body to move through a wall every now and then. The body has to be in constant motion and constant rotation for ths to happen and it doesn't happen all the time but when it does, and when it does, its a game killer. So, seeing as it dropped the ball, its warming the bench on the side-lines. Maybe next year it'll be a star but not this season.
nevertheless, I will explain how it works though I can't explain why it doesn't always work. nor why reloading the exact conditions and stepping through again does not cause the same bugs as earlier. probably my loose definition of 'exact conditions' has something to do with it as there is nothing random in the algorithm and it should just work or not work but for some reason it just doesn't and I'm just going to move on with this project without it anyway.
in any case, the failed move() function divides its task in two parts in a way very similar to the rotation function : point-vs-edge & edge-vs-point. The point-vs-edge test tests the trajectory of the polygon's individual points against the edges of the walls. Finds a collision, measures the distance beyond which it has travelled when this causes a collision and then pushes the polygon back. The edge-vs-point tests are very similar but not. the same but different. these tests all rely on line-intersects-line tests and then measure the distance the polygon needs to be pulled back by drawing a line along the direction of motion from the point's end position and crossing it with the edge of the wall to get a point of intersection. Then it measures the distance between the point of intersection away from the point's end position along the path of motion and that's how far it has to pull back.
Things work good when nothing is rotating and you'd be hard pressed to rotate the object with the mouse wheel trying to cause a bug but when the polygon is constantly rotating and moving along colliding into walls it takes less than a minute for this bug to occur.
now I get to build a teleporter. this'll be fun. and plugging the various rooms of a space-ship together using these teleportation devices should be a bit of a trip. and by then we'll have astronauts moving around the ship, entering the docking bay, slipping into a fighter vessel and opening the outer-bay doors to undock from the shuttle.
freedom at last! freedom at last!
Dec. 23, 2010
there was a problem with the source code. I tested it using the StructureInterior_Bunker.xml file and it was working fine but never bothered to test-run with the default square 'new' polygon and only later realized it had major issues with parallel lines and vertical/horizontal walls. The issue had to do with
classMath's LinesIntersect() function which failed in these cases.
there were a few problems with the game itself. annoying little bugs. I went to the hardware store and bought a can of bug-be-gone. there'll be more but I'm on it.
Mars Mission 4