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