Path-Finding, AI Plans

Like I said in my last post, the AI doesn't path-find very well.  It will head directly towards the player's location without creating a path around obstacles.  Well, it will eventually go around them, but it will go as far as it can before it has to start moving around it.  This works well enough on a map with little or no obstacles, but every other map gives the AI quite a bit of trouble.  Like I said, it eventually makes it around, but it's messy and not very intelligent.  Also, it's not very fun to play against because its offense is slow and it fills up the area around its home base with loads and loads of routes that you have to tediously make your way through.  Better path-finding would mean the AI would build its routes with more purpose and strategy rather than trial and error.

I've been brainstorming what would be the fastest way to do it.  I've known for a while now the the AI will calculate where it thinks its enemy is and send all of its routes in that direction.  The trick is doing the path-finding for each route quickly and efficiently.  I originally thought I'd just do an A* path search from each node one after another, but I figured that would quickly slow things down when the AI's routes get bigger.  Then I had an idea.  I could use Dijkstra's algorithm, starting at the end point and run it until it finds all of the nodes.  I can save alot of time and resources that way, sharing the processing time between all of the nodes at the same time.

The one issue with this method that I can see is that if there's a node that cannot reach the destination, the algorithm will keep running until it has tested every point on the map, which really really slows things down.  My solution is to run it until it finds one of the nodes, and then set a time limit for the next one.  For example, after one is found, it will only test 100 more before it ends unless it finds another in that time, in which case the time limit will reset back to 100 again.  That way, it will stop when it thinks that it has found all of the nodes that are actually reachable.

I'm excited to get this working.  It will really open up alot more possibilities with maps.  After that, I want to give the AI a state machine.  At the moment, it is always in attack mode.  Eventually, I want it to have modes like "Scouting", "Offensive", "Defensive", etc.  I want there to be routes that only attack you when they are attacked first, or routes that attack on sight, or routes that only attack if you're close, but stop when you back off.

I was hoping that at this point I could really take off with designing levels, but with a messy AI, it's just not very fun yet.  I like to think that once the AI starts acting more intelligently and is more flexible, the levels will start popping out of their own accord.  However, after the AI is beefed up a bit, I'll probably pull all of my time into integrating scripting into the engine.  It's something I've never done before, so I don't know the best practices.  I'll have to do some research.

Anyway, it's moving forward slowly but surely.  I can't wait for all of this "under the hood" stuff to be behind me so I can really start experimenting with the actual game.

Thanks for reading!
clevceo

Editor, Fog of War

The editor saves and loads now.  I know it's a stupid little thing, but it was exciting to save a level and open it again.  Also, I tried to make the file browser as convenient as possible.  I even added the path buttons at the top (a button for each folder; if the user clicks one, it backs up to that folder).  However, the scrollwheel doesn't scroll the listbox.  Instead, it just zooms out on the map in the background.  It's not that big of a deal because I can just grab the scrollbar and scroll fast that way, but I forget every time and try to scroll.  It's really annoying.  I think I'll add it just so it stops bothering me.

I tested the editor by making a level with the player and the opponent on opposite sides of the map.  It was exciting to actually play a map created with the editor.  However, there was an issue that I hadn't run into before.  Previously, I always had the player and the AI really close to each other on the map, so I didn't have to zoom out so much to see what was going on.  However, with the players so far apart, I zoomed out quite a bit on the new map.  Unfortunately, this meant that it was displaying alot more fog of war than usual.  This was a problem.

The way I implemented the fog of war was using a simple grid.  Initially, every square in the grid is considered unexplored.  When a new node is built, a circle is drawn in the grid, marking each square in the circle as explored.  When the fog of war is drawn, it just draws a black square on the unexplored squares.  When zoomed out over a large map, that's alot of squares to draw!  The framerate dropped considerably.

I searched the internet for solutions.  One said to stop the camera if it tries to enter unexplored parts of the map, so you don't even have to draw any fog of war.  That's a hack, in my opinion.  Plus, it would be a pain to play the game with that constraint.  However, that's the only optimization I could really find for actually "drawing" the fog of war.  There were plenty of articles about everything else concerning fog of war.  Maybe if I looked for a few more hours, I would have found something.  However, I was tired of looking.

I had an idea that I wanted to try.  I saw that there were big portions of the map that were completely covered in fog, and you could cover most of it with one big rectangle.  So I decided to try to fill up the fog with as many big rectangles as possible, and fill in the rest with smaller rectangles, thereby reducing the number of sprites to draw.  I wasn't sure if it would be faster because it was more processing (though the algorithm is as optimized as it can be), but when I tried it, it was lightning fast!  Fog of war no longer even comes close to lowering the framerate at all, even when zoomed out all the way.

I was really surprised that I didn't see this trick online.  I'm sure it's somewhere out there, but it should be more common because it worked extremely well for me.

My next step, I think is to put some work into the AI.  My currently AI doesn't path-find well enough for most of the maps that I'll be making, so I'll be improving that.

Thanks for reading!
clevceo

ListBox

I decided that in order to make a good save/load window, a flexible listbox control would help tremendously.  After I finished up the geos, that's what I began working on.  I finished it today...or at least I finished the base control.  I might make a custom control on top of it for the save/load window, but I'm not sure yet.  I also implemented the double-click event so that it can be navigated similar to windows explorer.  I just want to make my life a little easier, that's all.

I've created the window and you can open it and close it, but it doesn't do anything yet.  That's the next step.  It's taken alot more work than I expected just to get to this point, but I'm here.  Hopefully the next part doesn't take as long.  We'll see.  I wish I was past this so I could start building levels already.  But I'll be there before you know it.

Thanks for reading!
clevceo

Editing Geos

Man, the geos were tougher than I expected.  It turns out that I was almost done with the code before I realized that I'd made some big mistakes early on that affected almost all of my code.  Basically, I forgot how the vertices were stored.  The vertices in the geos are stored in pairs for each line.  For example [50,0,0,50,0,50,100,50] is a triangle with the vertices 50x0, 0x50, and 100x50.  However, I forgot that and thought each vertex was stored only once ([50,0,0,50,100,50]).  I didn't try to do any collision testing against them or display any textures on them until the end, so my error didn't show for a long time.

I got that fixed, though it took alot of debugging before it was working right.  And after that, some old errors that I didn't know about surfaced.  Fortunately, these ones were sort of expected.  They had to do with breaking the shapes down into triangles in order to draw them.  A triangle geo won't need any breaking down and a square will be only two triangles, but a complex shape requires some deep thinking to break down.

Because it's alot of complex math, it's easy to overlook things.  While one shape might be broken down just fine, another might present a case that I hadn't thought of and it will either draw incorrectly or crash.  After alot of bashing my head against my desk, I got it working.  It works flawlessly now as far as I can tell.  I just have a couple more things to do with it before I start on the save feature.

I know this post wasn't all that exciting (as usual, lately), but soon I'll have more exciting news to share.  The editor is the boring hurdle that I need to get over before things take off.  I won't be working on it again until Monday, however.  But stick with me.  Thanks for reading!

clevceo

Editor (Continued...)

I'm still hard at work on the editor.  Today I finished all of the route editing portion.  It took me a good while, but that part is done.  Once again, I probably put too much work into making it intuitive and foolproof, but hopefully it makes the level editing faster and easier in the future.

The next step is the geos.  It shouldn't actually be too hard.  I just need to allow the user to add, move, and delete vertices.  Also, for convenience, I'll probably add a way to move the entire geo at once.  The vertices in a geo are world coordinates rather than being relative to the upper-left corner of the geo, so moving an entire geo would mean moving all of its vertices simultaneously.

I'm stoked for the geos to be complete.  Once they're done, I can work on the save feature, which shouldn't be too bad.  Once that's done, I can finally create levels quickly and try them out.  At that point, I'll probably start posting more often because there will be alot more to talk about.  Also, I'll be going back into the engine and improving the AI, experimenting with new mechanics, etc.  It's exciting.

Thanks for reading!

clevceo

Editor

I decided that I didn't absolutely need the listbox control, so I decided to get started building the editor.  When I need the listbox, I'll build it.

Until today, all of my time has been spent just putting together the gui for the editor.  I probably spent more time than I had to, actually.  I put some work into the textboxes so that they validate your input.  I could have just left it, but I'm hoping that it will save time and frustration in the future.

I started building the rest of the editor today.  You can add nodes now, though you can't modify or delete them once added.  It's not that special yet, but now that the gui is done, it's going to progress quickly.  I'm excited for the day when I can load and save levels and actually try them out.

I've been thinking of more ideas for levels.  I'm itching to finally try them all out.  I wish the day was here already.

Thanks for reading!

clevceo

Graphical User Interface (Continued...)

Today, I made some good progress on the graphical user interface library.  Specifically, I completed the two most difficult controls that I'll need: the textbox and combobox.  Next is the listbox.

This library does something that my last one didn't.  When I built my previous library, I didn't know how to clip graphics at the edge of the control.  In other words, if there was too much text on a button, it would spill over the sides.  I thought you had to create a buffer the size of the control, draw on it, and then copy it to the screen.  I found out today, however, that you can use a "scissor rectangle" to clip the edges.  Basically, you say what part of the screen you want to draw to and it will clip anything that runs outside of it.

This doesn't make a huge difference with buttons and similar controls because I'm not going to put too much text in them anyway.  But it's really handy for textboxes.  In my last version, I just calculated how many characters would fit in the box and only drew that many.  This took more processing and wasn't pretty.  It will also come in handy if I ever need to build a scrolling panel.

I'm excited to finish the listbox because that means I'll be able to really start building the editor.  Before we know it, I'll be building levels willy nilly and Sever will be progressing much faster.

Once I have the editor up and running, I'll post screenshots.  If you ever have any suggestions or comments, please share them.  Thanks for reading!

clevceo

Graphical User Interface

I haven't really touched the gameplay since my last post.  Instead, I've been working on building a graphical user interface library for use in the game.  I'll explain why.

I feel like I've reached the point where I can really start experimenting with the mechanics of the game, but manually editing the levels with a text editor is really really tedious and I have to guess at the numbers and run the game to see what it looks like and then go back and tweak them until they look right.  Long story short, it's extremely inefficient and not fun at all.  That's why the latest videos have no geography.  It's just a blank space with two players in it.

Time to build a level editor.  With a level editor, I feel like I can experiment with level layouts quickly and test the gameplay to explore what's fun and what's not.  I really feel like this is the next step.

What was holding me back from building an editor before was the lack of a graphical user interface library.  I built one in 2006 or 2007, but I was too overzealous and it ended up being a big clunky mess.  I didn't think so at the time, however,  I thought it was the bees knees.  It was as close a copy of the WinForms functionality as I could get it, which is overboard for my needs, to be honest.  Because of the time I spent on it last time, I've had a good idea of how I wanted to do it, but it was a bit daunting.

However, I finally decided to stop dragging my feet and just build the darn thing.  The foundation is working now.  I have buttons, labels, etc. and they're working great.  I already like it alot better than my last one.  It's alot cleaner and smoother to use.  The next controls I need to build are the textbox, listbox, and combobox.  The listbox shouldn't be too bad, but the textbox and combobox will be a bit of a pain.  However, once they're done, building the game's and editor's interfaces will be a cakewalk.

After I'm done with it, I'll hunker down and build the editor.  After that's completed (enough), things should really start moving along with the mechanics.

Since the time is coming when I can start experimenting with different levels and even try to play with story a bit, my mind has been running wild with various ideas.  I have some good ones that I'm excited to try out.  I know it's probably a bit early for that, so I'm not setting anything in stone yet, but I think the mere act of experimentation and exploration will help me develop the mechanics of the game.

Thanks for reading!

clevceo

AI Threading, Route Density

The only thing I did with AI today was a quick optimization.  Being inexperienced with threads, I didn't realize that starting and stopping the AI thread with each cycle is costly.  It takes a little time and you could see a little stutter.  At the time, I wasn't sure if that was why it was stuttering, but I decided to change the AI so that it runs on a continuous thread and just loops while it waits for new info from the main thread.  I wanted to see if that would fix the stutter.  Sure enough it did.  It runs silky smooth right now.

The other change I made was to the balance of the game.  Specifically, it had to do with the density of people within the routes.  Before I explain the change, I'll explain the purpose that the people play in Sever.

The little builder people that run through the routes and build new segments exist as a resource.  The idea is that more you have, the faster you can build.  They are produced at a regular rate from the parent nodes, so you don't have to create them yourself like you would in other games.  Instead, it controls the player's pace in the construction of his routes.  If he builds faster than his people can be produced, then the people are too spaced out and don't build as fast.  This is especially crucial when actually fighting the enemy.  The one with the fastest routes has the advantage.  On the flipside, if he expands too slowly, he might reach full capacity and production will stop.

This causes the player to want to protect his people.  Some are lost in defending and attacking, but the less the better.  The more of the enemy's people are destroyed, the more of an advantage the player has.  Also, to prevent the enemy from replenishing, the player will want to keep attacking until the enemy is destroyed.  Otherwise, the enemy could make a comeback.

Having more people also allows for more strategies.  For example, if there are enough people in a segment that is aiming to intersect an enemy's segment, and the player needs to use that segment slot, he can split his own segment, freeing up the slot and allowing the end of the segment to run into the enemy like a projectile.

As long as the player continues to expand, production will likely never stop, so that's a rare issue.  However, density can still get really low.  Sometimes when fighting the enemy, the player can't help but expand quickly and lose lots of people.  In this case, the player can restore his density by retracting unneeded route segments.  Some players might even make a stockpile of them behind their base so that they have them when they need them.

That was the plan for the people when I was first thinking through Sever's concept.  This would only work if I could get the number of people to really matter and make a difference in the game.  Until now, the density made a minor difference.  Expanding fast and overwhelming the enemy with lots of slow routes coming at them was more effecting than precision attacks with a few fast routes.  Changing the rate at which people move, build, or are generated didn't make a difference.

I knew that if I couldn't fix this issue, then I should probably cut the people and have routes build at a smooth fixed rate.  I could do that and make the game work, but there would be alot less depth and strategy in the game.  Overwhelming the enemy with tons of attacks would be the primary objective, and the AI is an absolute pro at that.  But humans can't make issue commands as quickly as the AI can, so that puts the human at a disadvantage.  And besides, it's just not as fun and allows for less variety and styles of play.

I knew that to reward the player for having more people, I'd have to make the difference between a sparse route and a dense route wider.  I came up with the idea to make the people in dense routes move faster and sparse routes move slower.  I've implemented it and it works.  The AI went from unfairly hard to beat to alot easier.  However, the advantage is slightly on the player's side now.  The AI just throws routes at the player without even thinking about density.  Next, I'll have to get the AI to be a bit more picky with construction and retract unneeded segments.  We'll see how it goes.

Thanks for reading!

clevceo

Sweet AI Update

Good news!  I tweaked the AI and it's beautiful!  Of course, it can be improved (it leaves its backdoor open, which is honestly the only way I can beat it right now), but it's hard!  I had to play it over and over again to get a good video of me beating it.  However, I decided to include one of it creaming me as well.  It moves fast, much faster than I expected.  It's really exciting to see it working so well all of a sudden.

First, watch it destroy me (fog of war is faded so you can see what the AI is doing).  It's hard to see exactly how it beat me, so you might need to expand the video.  If you'll notice, after a segment is split, the end that was cut off still has a short amount of time to run into an enemy segment before it shrinks into nothing.  In effect, it turns into a short range missile.  Watch the AI take advantage of that when he takes me out.



Next, watch me exact my revenge.



I'll bet you're glad the big pink thing from my last video is gone.  Unfortunately, It will be back soon.  However, I might change the texture so it doesn't look so bad.  You might also have noticed that I've tweaked the colors.  The AI is red and mine are light blue (green when building a new node).

I think today's update is proof of Sever's promise as a fun game.  There are definitely some issues I need to consider as I move forward, but all of my fear that the AI would be too hard to implement are gone.  I may not be able to create a genius AI, but almost all AIs are exploitable, so I'll be in good company.

It's nice to finally have something interesting to show.  Hopefully I'm not the only one that thinks so.  Thanks for reading!

clevceo

AI Working (Enough)

The AI syncing works.  There were a few hiccups, but I figured them out.  It now tries to attack the player.  It's still not very smart at all, but it avoids obstacles and consciously aims for the player's routes.  It's somewhat easy to beat since it's so predictable.  In other words, it will aim a route at one of my segments, I'll block it, and it will repeat the same move over and over again until I do something different.  Meanwhile, I'll have another route circling around the back and flanking him.  It makes it pretty darn easy since he doesn't consider defense at all yet.  Nevertheless, it's real fun to see it actually having a strategy and making moves that aren't scripted.

From here, I want to create a level editor so that I can test the AI in different environments without manually typing up all the level data like I did for the one you saw in the screenshots and video.  It looks simple, but when you have to type it all out, it's not so simple anymore.

I created a level editor once before in a previous version of Sever, and I think it was pretty good.  However, I was using a custom GUI library that I had created.  I don't know if I want to pull that out again because it's way too complex for my purposes.  I was a bit overzealous.  I can probably make something much faster and simpler from scratch.  Unfortunately, it's going to take a little extra time to do.  But it will be worth it.

I know this blog is really boring because I'm still building the core game engine, and I understand if no one actually chooses to read it much just yet.  If you've read this far, however, I'm hoping it's because you're at least somewhat interested.  But please check back periodically to see the progress.  Hopefully you'll eventually start to like what you see.  Thanks for reading!

clevceo

AI Syncing Continued

Today, I got the AI syncing ready for testing.  It runs, but I don't know yet whether everything is syncing correctly.  It was a very tedious process to get it to this point, so I'm excited for it to be over.  I'm sure I'll be making modifications in the future, but I have the foundation completed.  Hopefully I'll just be making small revisions or adding to it in the future instead of rewriting everything.  But I don't think I will, because I really think it's a good system.

I'm debating whether I should just build a simple AI and the networking, and then put all of my focus into just experimenting with the mechanics so I can evolve the gameplay.  My reasoning is that I might write an entire AI only to either rewrite it to fit new mechanics or never evolve the game because I don't want to rewrite the AI.  I could instead build a simple AI and rely on networking to test the gameplay.  However, at the same time, I don't yet have someone to test it with, so I'd have to either find testers or another developer to work with before I can move forward, and I really don't want Sever's development to be dependent on anyone's time other than my own.

The other possibility is to try to make the AI flexible so that I can easily modify it to work with new mechanics.  I'm not sure.  It's a bit scary, to be honest.  But I don't want to give up just yet.  One thing that's encouraging is that I don't plan to change the mechanics that much.  I don't want to add features willy nilly.  I'll only add mechanics that I think will feel true to the game mechanics, like they belong.  The game will be hyper-focused on the core game mechanics and will merely try to explore every possible situation presented by those few mechanics.  This will keep the game tight and smaller than most RTS's.

I'm scared again, but I pushed through last time, and I plan to do it again.  Thanks for reading!

clevceo

AI Syncing

I've been putting alot of time into updating the AI's version of the world each time it cycles.  I mentioned in the last post that I was working on having it compile a list of world events and letting the AI apply them to its own version of the world.  That feature is close to completion.  I have the list of events compiled and sent to the AI, but the AI doesn't interpret the data just yet.  That's the next step.  It feels like alot of work, but it's definitely worth it.  The game used to hang for a fraction of a second every time the AI cycled, but now it's seamless.  I've completed all the work that the main thread will do, so this should be the final main thread performance (AI-wise anyway).

Once I have the AI interpreting the data, I can really start working on the AI decision-making.  It's tedious, but really exciting.

Thanks for reading!

clevceo

AI Decisions

I've noticed a few issues with my current setup.  First off, path-finding with distance approximation creates a similar path to the Manhattan Distance Heuristic.  In other words, the fastest way from point A to point B is more like an L.  First you move at a 45 degree angle in the general direction of the target until you are parallel to it either horizontally or vertically, then head straight for it.  This works, and it works fast, but I really want my AI to move in straighter lines.  So, unless I change my mind, back to the original heuristic.

Next, taking a snapshot of all state info for the AI every few seconds takes alot of time and memory.  I knew this would come, but I wanted to focus on it later.  Unfortunately, it kills the performance already, when there are only 8 nodes on screen.  I've decided to merely keep track of changes to the world and sync them with the AI.  The data transferred to the AI will be things like 'segment id 2's length changed to 150' or 'node id 7 removed'.  Of course, it won't be passing text, but you get the idea.  It will pass minimal information and it will be up to the AI to do all the processing involved to update its current snapshot.  This means alot less processing on the main thread and alot less information passed to the AI.  The AI will have to do a little more thinking, but that's okay.  As long as the player's experience is smooth, I'm happy.

I've been thinking about how the AI will plan his routes as well.  I've been entertaining the idea of using genetic algorithms again.  I'm pretty sure they'll be too slow, but I want to give them a try.  I may as well try everything, you know?  What if I'm surprised or it leads me to a better idea?  I may even end up doing a hybrid of multiple different techniques.

Today, however, I focused on trying to get one path built from the enemy to the player.  I wanted to use actual pathing rather than a fixed route that only works on one map.  In other words, I want the AI to be just as effective as my last one on any map I create.  Now, remember that it's only building one line of nodes and segments, it doesn't defend itself, and it only tries to attack the segment connecting the player's parent nodes, nothing else.  It will still be stupid, but once I get it working, I'll be a step farther in route planning.

Ultimately, I want the AI to be able to make up its own mind about the map's layout.  I don't want there to be any map-specific scripting that aids the AI's strategy and tactics.  I want to be able to drop it into any map at all and have it still be just as effective as any other.  What attracts me to genetic algorithms is that I don't have to think up every strategy beforehand.  It can come up with them itself.  It still has its limits (besides inefficiency), but as long as I can tell it what's a good move and what's a bad one, it can come up with more creative strategies than I ever could.

I may create the genetic algorithm alongside any others I work on and see which turns out best.  Initially, I'm pretty sure the genetic algorithm will be the slowest, but that's because I've never actually built one and there are so many different ways to do it.  I'll have to experiment and try to optimize it until I either decide its fast enough or it will never be fast enough.  I'm crossing my fingers for the former.  I'd love to create an emergent AI.

Anyway, thanks for reading!

clevceo

Math Optimizations

I've been avoiding optimization for a while now.  I used to think optimization was the secret to life, but then I listened to a lecture by Jonathan Blow where he said that it's rarely necessary when we think it is, and it takes forever to do, so it's usually a waste of time.  However, after reading through Christopher Park's (developer behind AI War: Fleet Command) blog, I've decided to optimize just a bit before I move forward.  Because Sever's AI will work similarly to a standard RTS, speed is of the essence.  I need the AI to think fast and not lag too far behind the human player.  Also, these optimizations should keep things synced between clients in a multiplayer game.

First off, I changed the primary data type that I was using for all of the math.  I was using the float datatype because that's the default type used in MonoGame.  If I was more educated, I could probably tell you why.  But alas, I'm not.  Anyway, Christopher Park had an issue with syncing and created a truly fixed-point struct that apparently did the trick.  Rather than waiting until I have syncing issues, I decided I'd start early and do the same.  It took a bit to get it working correctly because I had to go through every single stinking class in the game and change Vector2s to my new VectorF struct and floats to the new FInt struct.  I also made some modifications to his version of FInt to make it do what I wanted it to do.

If you want to know more about fixed point math, look here.

I got it working, and I haven't noticed any performance improvements, mostly because as an early prototype, it rarely goes under 60fps anyway, which is actually probably too high.  I'll probably lower it for the sake of processing power.  60fps is more important for shooters and stuff like that.  RTSs can sacrifice a bit to make room for non-graphical processing.  Anyway, I trust that using fixed point math will help out in future versions, whether I notice it or not.

Also, he talked about distance approximations.  Square roots are slow, and finding the distance between two points requires a square root.  Finding the distance between a point and a line (a common operation in Sever) requires 4 square roots!  When drawing graphics, you need exact numbers, but when doing collision testing, you can first use an approximation, which is enough to tell if the points are close enough to do the real distance calculation.  In the end, that's more math, but 90% of the time it doesn't get past the approximation, so it really saves time when doing collision testing against a hundred objects, most of which are far away and don't need precise calculations to know that they don't collide.

If you want to learn more about distance approximation, look here.

While I'm not sure how much I'll notice a difference in performance as a result of the switch to fixed point math, I'm pretty sure that the distance approximation is going to make a big difference in both collision testing and path-finding.  In both, there's usually alot of wasted distance calculations, so this should soften the blow to performance quite a bit.

That's all that I've done since my last post, besides play against the AI over and over.  Hopefully my next post will be more interesting.  Thanks for reading!

clevceo

My First Gameplay Demo Ever

That's right, I have a gameplay demo for you.  Yes, that also means that it's somewhat playable.  The AI fights back.  It's really stupid, and it only works on the one map that I've made, but it does the trick.  It's actually about 4 lines of code.  However, it proves that my AI setup works, all except for the actual thinking part.  I'll probably make plenty of modifications in the future, but the foundation is done and tested.  This is a pretty big milestone for me.  I know I've said that before, but this takes the cake.  I've never had an AI to play against, and it happens to kill me almost every time I play.  He's easy to kill, but he takes me out before I can finish him off.  Here's the video:

It still looks like the screenshots, except the color of the opponent.  Sorry his routes are a bit hard to see.  I would change it, but I've already uploaded the video.  At least I made him a different color.  Otherwise, it would look really confusing.

Anyway, you'll notice that he keeps attacking even after I've split his parent nodes, which destroys the system in a chain reaction.  Watch it twice, the first time watch me take him out, and then watch him attack me.  I make the first strike (he doesn't defend himself, so it's not quite fair), and I keep trying to stop him from attacking me, but he gets me in the end.

This AI follows a decision tree with two branches, and it always builds from the last node created (starting with the bottom-left node).  If the AI controls 4 nodes, build 350 pixels to the left.  Otherwise, build up 200 pixels.  Like I said, it's stupid, but it works great for this video.  It really looks like it's trying to beat me.

Let me know what you think.  I'm really proud of this milestone.  Thanks for reading!

clevceo

AI Progress

This is a really short update.  I've done some good work, but it was all on one thing and it can be explained fairly quickly.

I've made a little progress on AI.  It doesn't work yet, but I've begun setting it up based on what I've read.  There's now a thread that runs for each AI player and does all of its thinking.  So that I don't have to worry about making things thread safe (which is both messy and inefficient), I take a snapshot of everything in play and send it to the AI to process.  This is also necessary because I can't have the world data change while the AI is looking at it.  The snapshot isn't 100% complete.  It's only what the AI will need to do its thing.  That way, I can save a little time and memory.

Before I did that part though, I made all player actions command-based.  This cleans up the player interaction quite a bit.  I'm liking the changes.

It's all a bit of a mess at the moment, but hopefully it will come together soon so I can build a simple AI to play against.

Thanks for reading!

clevceo

Articles

I'm at a point in Sever where I can't just keep building without stopping and making a plan.  I mean, there are a few things I could do, but I'd basically just be killing time before I move to the important stuff.  This is the wall I hit in projects that usually stops my progress short.  However, I imagine I'll hit this wall with every project I ever work on.  The difference between the successful projects and the failures will be whether I chose to climb over the wall or not.

It's a bit scary thinking about that.  I've done it too many times.  Anyway, rather than giving up just yet, I'm choosing to do a little research that will hopefully give me what I need to move forward.  In particular, I'm reading up on RTS networking and AI.  Sever isn't nearly your typical RTS, so I'll have to pick through the AI articles for anything that might apply, but the networking methods should be very relevant.

I didn't realize that networking for an RTS might work differently from any other multiplayer game.  However, it makes perfect sense once I think about it.  Basically, the game runs in steps, and each player gets to decide what moves to make, and all moves from all players are executed at once, and then on to the next step.  Many games communicate states of units back and forth, while RTS's typically communicate unit commands.

Because there are so many units, it would take up too much bandwidth to send the unit states back and forth for so many units.  Because they only communicate each players' commands to each other, each client computer has to run his own version of the simulation and each has to be in sync.  This is the only practical way to network a game with so much going on.

With that in mind, I'll have to rethink how I've been planning to run Sever.  I'll have to make some changes to make sure it runs in steps.  I'll also have to have all player input be sent to the engine in the form of commands.  I think I'd like that anyway.  It would simplify player interaction and how I build the AI.  Here's an article about this sort of thing from the developers of Age of Empires.

About AI, I read a few articles by the developer of AI War: Fleet Command.  I've never played the game myself, but I found the articles fascinating and I'm tempted to try the game out.  I don't know how much will really apply to Sever, but it's given me some ideas to try.  Basically, his intent with the AI was to avoid traditional decision trees.  Instead, he gives each individual unit a little bit of intelligence and has it make its decisions based on what the units around it are doing.  He did this in hopes that the AI would have "emergent" behavior, as he calls it.  In other words, he didn't want all tactics and tricks that the AI uses to be pre-programmed.  He wanted them to think for themselves and do things even the programmer hadn't thought of.

In order to do this, each unit needs to do some number crunching about what's going on around it.  This particular developer uses LINQ to run queries in order for each unit to make a decision.  I've never used LINQ, but I have been reading up on it a bit.  I write SQL every day, so it shouldn't be too bad.  Also, this method apparently requires less code to write than the typical humongous decision tree.

Again, I'm not sure if I'll use his method or not, but I think I might at least try.  I won't be able to make every node autonomous because of how crucial every move is in comparison to a typical RTS where a unit can simply turn-around and go the other way if he makes a mistake.  It will really have to be almost 100% hive-mind, but I think I can try out some of the principles he explains.

At the moment, networking might be the easier path to take.  I'll start by making the game run in steps with commands, and then I'll try to develop some simple networking code, at least enough to be able to connect by LAN.  I really think it will be important for me to actually play the game and see what strategies work and what doesn't before I can really build an AI.  I understand the mechanics of the game and I have some general ideas about what strategies might work, but when it comes down to it, I know even more strategies for typical RTS's that I'm terrible at.  So it's pretty important that I actually play the game (alot).  Once I get the networking working, maybe I'll recruit somebody to help me test it.

I'm hoping in the testing that I'll have more epiphanies.  I really need epiphanies right now.  I've also been listening to lectures by Jonathan Blow, the creator of Braid (one of the best games, highly recommended).  He says a good way to make a game is to build it around a good idea.  For example, Braid's good idea is time manipulation.  Throughout the game are time puzzles, which evolve as you progress.  A more famous example is Portal.  Portal has (or had, until Portal 2 added more) one cool mechanic that the entire game revolves around.  Rather than trying to come up with as many cool ideas as they possibly could, like most games, they just explored that one concept fully and cut out all the extra content that didn't contribute.  And the results were great.

I guess what I'm saying is that I think I have a good idea, but I haven't explored it.  I think there's so much more than networking and AI that will be put in this game.  However, I think they're the minimum.  Once I have at least enough of both to be able to play the game, I want to start experimenting.  I want to try everything out and see what sticks.  I want to try building puzzles in the game.  I want to build a typical RTS map and duke it out with another player.  I want to add different kinds of nodes with different properties and see how it affects gameplay.  I don't think it will turn out like Braid or Portal, but I want to at least use their method of building a pure game and see if I can do the same for mine.

I know that wasn't much of an update, but it's what's on my mind at the moment.  Thanks for reading!

clevceo

AI

Since I got the path-finding working, I've been thinking about how the AI will make decisions in the game.  I've thought about measuring each nearby path-node based on its offensive and defensive value, and then testing all the different possible moves it could make and picking the best one.  It could be done, but it wouldn't be very efficient.

Today, I had an idea that might work.  The AI will have different goals and each goal will be given a priority based on the current situation.  For example, If the enemy is close to the AI's base, defense is given priority.  If the enemy base is found, and the AI's base is safe, then offense is given priority.  If the enemy has not yet been found, then scouting is given priority.  The AI cycles through each goal in order of priority and determines if it wants to make another move toward that goal.

Scouting mode will look for nearby fog of war and build nodes near it to clear it out.  Offensive mode will do one of two things: if the enemy is close, attack it; if the enemy is far away, close in on it.  Lastly, defensive mode will either fortify the base or fend off attackers.

Whenever a goal is examined, it determines whether another move needs to be made or whether it should wait for something to be completed first (a segment to finish building, for example).  In order to determine what move to make, it needs to assess how good its current state is, and what can be done to improve it.

Today, I've been focusing on how the defense assessment could work.  For the most part, a decent defense just means that there are nodes on the outer edge of the base with segments to spare.  In order to see how the current defense is, I need to determine which nodes are on the outside of the base.  This is tricky, but I think I came up with a solution.  Here are a couple screenshots.  I'll explain them afterwards.

First off, I'll find the left-most node, draw a horizontal line to the left and rotate it counter-clockwise until it hits another node.  Then, I'll duplicate that line and rotate counter-clockwise again from the second node to the third node.  This will repeat until the entire system is outlined.  These are the nodes I'll test.  If I find too much space without a node that can attack, I'll try to fix that problem.

You'll notice that there's a big pink object in the middle of the base.  Obviously, I won't need to place defenses around it.  That would be a waste.  So I'll probably let the line hit these objects as well and rotate around them until I hit another node.  Of course, anywhere the line touches the object will be considered well-defended.

Also, this outline will envelope all scouting and offensive routes as well, so I'll have to find a way to section it off.  Sectioning off the scouting routes might be easy.  The segment length requited to build a scout node will be longer than the line, so the line will pass straight through the segment and hit the next node in line.  Offensive routes however, will need to be separated somehow.  I'll cross that bridge when I get there.

Thanks for reading!

clevceo

Path-finding

The last two days have been spent trying to get the path-finding to work.  It finally does, but it took longer than it should have.  First off, I worked off of examples from a book called Programming Game AI by Example by Mat Buckland.  Let me start by saying that it's a great book.  It has helped out a ton.  However, all the examples are in c++, and while he shows most of the code, some of it you have to get off of the included cd, which doesn't come with the kindle version.

Honestly, the hardest part was getting a working indexed priority queue to use in the algorithm.  The rest wasn't too bad.  I ended up using the A* algorithm, which he says is the best one if you have a specific destination in mind.  If you don't, it's easy enough to switch it to Dijkstra.

The problem with the indexed priority queue is that .NET doesn't have one built in for me to use, and all the code for it was on the cd.  I searched around the internet, but it was difficult to find one in C# that did what I needed.  I tried to translate one from Java, but I don't remember Java as well as I thought I did.  Finally, I found a good one, though it went a bit overkill and I had to simplify it a little bit so I could understand it.  I had to modify it a little and build a wrapper around it to get it to work with my path-finder, but it works now and that's all that matters.

I don't know if the algorithm is 100% optimized or not, but I'll figure that out later.  Right now, I'm just happy that it's working at all.

For testing purposes, I just had a path traced from the top-left corner of the map to the cursor.  That's why it looks like a pointless path.  Also, if you're not familiar with path-finding, you might be wondering why there are so many paths branching off into nowhere.  Because computers are computers and not humans, they can't instantly see paths from point A to point B like we can.  Consequently, it has to test tons of different paths until it runs into the destination.  In most path-finding algorithms, there would be many more paths going the wrong direction, but this algorithm eventually narrows the search at the end.  The only reason why it's not narrow at first is because of the big obstacle in the way.

Next, I'll probably build an extremely minimal AI that will just build a straight line toward the player's routes.  Even though it's so simple and should be so easy to beat, this is still particularly exciting because it will be the first AI I've ever built for Sever.  For the first time, there will be an opponent to play against.

Eventually, when the AI is more fleshed out, it probably won't have specific destinations it wants to find.  Instead, each node will have a score based on how safe a node would be if built there, how close it is to where the AI thinks the enemy base is, whether or not it will clear out fog of war, etc.  Also, I'll have to do this for all nodes with empty connections to spare, which will use more processing power, so I'll probably have to make it run over several update cycles rather than busting it all out at once and lowering the frame-rate.

Thanks for reading!

clevceo

Node Types, AI

There's not much new to show in a screenshot, unless you want to see a bunch of debugging graphics that will normally be hidden.  But I won't bother you with that.  This will be a short post anyway.  Just popping in to share a little progress update.

There are now a set of different types of nodes that you can build, and the way you choose which to build is by the distance you place between it and the node it leads from.  In other words, there isn't some menu that allows you to choose the node type.  You can't press a number key to select which node type you want to build.  If you want to build a certain kind of node, you have to drag a certain distance away from the node you're dragging from.

That might sound unusual, and it's very possible that I'll give this idea up for a different one later on.  However, I'm sticking with it for now.  Here's why:

Previously, you right-clicked to cycle through the different types of nodes.  This isn't terrible relative to the ways you traditionally choose weapons in an FPS.  In fact, I may have mapped number keys to different kinds as well later on.  Many gamers may have felt at home with that method.  However, I had some qualms with it.  First off, having to right-click three times or reach up and press a number key every time you wanted to build a certain node felt tedious and forced.  Also, while right-clicking is easy and the player wouldn't easily forget it, but nobody would ever know about it without first being told.  From day one, I've wanted this game to feel so intuitive that the player could just start playing without any tutorial.  Of course, this may have been wishful thinking and it may be impossible, but I don't think it's such a bad idea to get as close as I can.  All in all, it just didn't feel right.

For a long time, I thought I'd be stuck with that method because there really wasn't anything better that I could think of.  However, one day I thought about the selection by distance method, and it played around in my head for a bit before I really set on it.  At first, I only thought about how much more intuitive it would make things, but I also started to think about how it would affect the rest of the gameplay.  For one, it would limit the way the player builds his/her routes.  The minimum distance wouldn't change anything because there was already a minimum distance for different types of nodes, but the maximum distance was a new limit that would drastically change playing-style.

At first, this scared me, but after a while it grew on me.  One of the main reasons I grew to like it was because it made each node type more unique in its use.  The distance became the cost of building the node.  Honestly, it just felt natural.  It fit.  It also simplifies AI a bit (which I've been thinking about quite alot lately).

Anyway, that's my current choice for node selection.  On to path-finding.

I'm starting on the AI.  I hit a point point where I could go one of three ways: add more features, start on networking, or start on AI.  There are some features I want to add, but I can easily add them after networking and AI.  That way, networking and AI will initially be simpler to code and I can just build on top of them later.  Networking would be really cool to do, but AI's been on my mind and I really don't know anybody that could help me test the networking at the moment.  I can test the AI myself no problem.

At the moment, I'm developing a path-finding system.  I've never actually done path-finding before.  I've read up on it, but I never got around to trying it out.  As I've been reading up on it, however, I've been thinking through how I could use it in Sever.  Normally, path-finding gets an agent from one point on a map to another.  It doesn't build a route system.  Because there isn't really a precedent for this kind of game, I thought it was a lost cause, but now ideas are starting to pour into my head about how I could implement it.  I'm really excited to get it working and have an opponent to play against.

So far, a map of possible paths is created and it takes all geometric obstacles into account.  However, it isn't yet able to do anything with it.  I'm still reading up on all the different algorithms, trying to determine which one is best.

I'm also reading up on genetic algorithms and neural networks, seeing if there's any way to use them in Sever.  Don't worry, I'm not just trying to find excuses to use them, but I think it's a good idea to explore them just in case.  They may just turn out to be the best thing that ever happened to Sever, but I'll never know if I don't look.

I guess this turned out to be a bit longer than planned.  My bad.  Anyway, thanks for reading!

clevceo

Geometric Obstacles, Fog of War, Collision Detection, etc.

I've been working my tail off on Sever.  Here's a screenshot.  Beware the ugly placeholder graphics!

There are a couple things to notice in this screenshot.  First off, the big ugly pink thing in the middle.  That is a geometric obstacle (geo for short).  It's called that because I'm unsure what else to call it.  I had geos in previous iterations of sever, but they were only for collision detection.  You couldn't actually see them.  Because of that, you had to attach them to sprites.  I didn't know how to display the shape itself at the time.  This time, however, I bit the bullet and researched how to do it.  Of course, they're going to look better than that because that's just a thrown-together shape with placeholder tiles over it.  Also, I'll probably add nice borders to them so they don't have those hard edges.

The reason why I didn't know how to do it before is because you can't draw them the usual way that MonoGame and XNA draw 2D graphics.  You actually have to draw it the same way you would 3D graphics, which I had never done.  This means you have to draw them in triangles.  As you can see, it's not a triangle, so I had to write code to take the shape and split it up in triangles just so I could display it.  It was difficult and buggy at first, but I did it and you can see it working in the screenshot.  I must say I'm proud of myself.

Next is the fog of war.  You can see two different shades at the moment.  The darker one will be black in the future, but since it's in development, I want to be able to see what's going on behind it.  Anyway, only nodes can see.  The route segments are blind.  The lighter fog you see is what a node I built earlier saw before I destroyed it.  So far, the fog is just cosmetic.  The game will still try to draw everything that's behind it.  I'll write that code soon.

Next, you'll notice the red circle.  This was in the last screenshot, but I don't know if I explained it before, but that's the currently selected node.  The red line and white circle leading from it are where my cursor is dragging a new node.

Lastly, you'll notice the dark circles around each of the nodes in the upper-left corner.  This is the required spacing between each node and every other node owned by the same player.  This way, players can't build them so close to each other.  However they can build them as close as they want to enemy nodes as long as they don't touch.

Oh, if you haven't figured it out yet, collision detection actually works now.

Anyway, that's my progress, or at least the interesting part.  I'll keep posting as it progresses.

Thanks for reading!

clevceo

It's Happening Again

Wow, I can't believe I'm writing this post.  I haven't touched Sever in so long.  For a long time, any efforts on any of my projects were short-lived, but this year I've put alot of work into both Idea and Sever.  You can look at my Idea blog to see what's going on there.  I'm a bit stumped on a few things, so I thought I'd give Sever another shot.  It's looking a ton more promising than it did in the past.

I just wrote the collision testing math today.  I haven't applied it to everything quite yet, but the hard part is over.  So far, there are only nodes and segments, no geography of any kind.  However, I've set up a robust system for handling the route systems and the people inside them.  It's simpler and better than anything I've written in the past.

I'm reusing bits and pieces of my previous code, like certain formulas I used.  However, there is one hefty bit of code I took and polished up.  It was a grid system.  Rather than collision testing every single object on the map, the map is split up into a grid, and each object is stored in its respective square.  When collision testing, only the relevant squares are tested.  That way, alot of processing time is saved.  It's a complex system, and I'm so glad I already had most of it written.

Things are working pretty well so far.  There are still some basic things I need to code before I really start moving forward.  I want to start on the network code fairly early on.  I also want to code some basic AI just for testing and fun.  I figure the earlier I start on these things, the earlier I'll find out I need to rewrite something.  It should save trouble later.  I made that mistake in the past, and I won't again.

The graphics are terrible, but that's placeholder graphics for you.

In the past, I was using Microsoft XNA for the graphics, but Microsoft has dropped support for XNA.  I tried looking around for an alternative and found MonoGame.  So far, it's good.  It doesn't do "everything" that XNA did,but it hopefully it will with future updates.  Plus, it's cross-platform, unlike XNA.  All that matters to me, though, is that it's doing what I need it to right now.

Anyway, thought I'd write an update.  Thanks for reading!

clevceo