Outpost 2 Coding 202: Part 1

[Sirbomber]

Part 1: Analyzing the Map - Distinguishing a rock from a hard place (so as not to get stuck between them).

Before the AI can do anything at all, it will need to be able to navigate the map and work with and around the map's terrain.

Here's a tentative list of terrain-based decision making the AI will need to deal with:
-Locate and defend at bottlenecks.
-Identify inaccessible sections of the map (eg that huge mountain in the middle of Around The World).
-Determine the "real" distance from a mining beacon to its base.  By "real" I mean "take into account obstacles like cliffs and rocks".
-Locate enemy bases.  This should be easy enough.
-Utilize vehicle waypoints effectively, since OP2's built-in pathfinding is horrible.
-Identify optimal base locations.

Bottlenecks
In a real fight, the AI is going to need to know enough about to defense to park its units at bottlenecks to keep the enemy out of its base.  All we care about right now is getting the AI to tell where those bottlenecks actually are, though, so how would we do that?
A bottleneck is, of course, a gap of passible terrain between two or more pieces of impassible terrain designed so that enemy units have to funnel into them, putting the defenders at an advantage.
Unforuntately, a lot of terrain matches the description of "passible between impassible" so we're going to have to be clever if we want to avoid getting false positives.

Anyways, let's look at a few examples of bottlenecks.  Some are obvious...




...Others, not so much.


Think of your favorite maps.  What do the bottlenecks look like?  Can we define a few general "structures" that will allow the AI to identify bottlenecks accurately?  Are there any similarly-shaped sections of terrain that might create false positives?  How do we distinguish these from real bottlenecks?

We need to think of criteria to look for when searching for bottlenecks.  Here are some thoughts, please add your own:
-A "bottleneck" should be defined as a line with two sectors of open terrain on both sides.  The line's endpoints must be impassible terrain.  Should we require the terrain on one side to be bigger than the other (be funnel-shaped)?
-Should we limit the number of bottlenecks we can have in close proximity to each other?  If so, based on what?
-Should there be boundaries (lower and/or upper limits) on the size of bottlenecks?
-Should we implement some kind of system to "rank" bottlenecks?  How do we determine what makes one bottleneck "good" while another one "bad"?

Note: Implementing bottlenecks this way may have the added benefit of dividing the map into several discrete sectors, where a sector is defined by an area enclosed by bottlenecks and impassible terrain.

Identifying Inaccessible Terrain: Because our AI isn't a Colony Searcher
So let's say the AI is playing a round on La Corrida.  It's in the bottom left corner.  To the left of its base, there are high mountains.  To the north we've got a valley.  Units can reach neither of these places.  This probably isn't going to be a problem, since pathfinding will just treat those as obstacles.

They will become a problem when we go to do a Land Rush though.  Say we're playing a custom map, and there's all sorts of ore mines down there because whoever made the map has a sick sense of humor.  If the AI doesn't realize that it can't get to those parts of the map, it may consider those viable base locations and never get around to actually building anything since it's hung up on reaching the unreachable.

So how do we check if part of the map is blocked off from the AI (since what is and is not "reachable" is relative to where the AI spawns)?  Beats me.  We could just pick an AI unit and check every passible tile on the map to see if the unit can reach that tile.  We'd need to figure out a way to optimize it though, or that will really bog down the game.

We're going to need to discuss this issue a bit more, and do some research.  BB/Hooman: if you're reading this, got any advice?

Simple Pathfinding: Determining the "real" distance from the base to a mining beacon
Look at this image:

We have two mining beacons near our Smelter: one at (220, 102) and the other at (238, 104).  If we just apply the distance formula (D = sqrt( [x1-x2]^2 + [y1-y2]^2 ) then the one on the left is closer.  Of course, in order to actually reach that beacon we have to go around a fairly large section of cliffs.  So we want the one on the right.  How do we figure out which one is "really" closer to us?

One option is to write our own pathfinding code.  _A_ recommended the A* pathfinding algorithm awhile back since it's pretty fast, works well, and is supposedly pretty easy to code.  There's plenty of info on A* all over the place, we can just Google it and pick a nice tutorial/demo/whatever.  But since this is all about discussion, if anybody else has a different suggestion please speak up.

Before moving on to the next subject, I will mention this one thing: if we implement A* right, we should also be able to apply it to units.  If we do it really well we may be able to overwrite OP2's horrible pathfinding system for use in regular play.  But don't hold your breath on this one.

Locating and Identifying Enemy Bases
Well, locating them is simple enough.  Just look for buildings owned by other players.  But how do we tell what types of bases they are?

I classify bases into a few different categories:
-Main base: Generally the player's starting base.  Should be the biggest one, and have all kinds of structures.  Key things to look for will be a Structure Factory, power, and non-strategic buildings (Agridomes, University, etc.).
-Sub-base: The only reason this isn't one of the other base types is because it doesn't have its own Command Center.  Instead, there's a (long) tube connecting it to another (probably the main) base.  Attempt to classify it anyways.
-Military outpost: If somebody has a bunch of Vehicle Factories built outside your base, and it's not you or your ally, you have 3 guesses as to what they're going to do with them.  No bonus points for guessing correctly.
-Mining outpost: Look for a Mine or Magma Well, Smelters, and a CC.
-Spaceport farm: This is probably behind the main base if terrain allows it.  Anyways, EMP Missiles are gonna be flying from this soon.

Of course, things don't always fit cleanly into those categories.  An ore base might have a few VFs with it, for example, so we would want to identify that as such.  I'll leave it to the rest of you (and ultimately, whoever decides to implement this part) to figure out exactly how many types of bases there are.

Anything else we can do here?  Let's see... Well, if we find their base we can search for bottlenecks and backdoors.  That would be useful in planning attack routes and predicting where they'll defend.

Anyways, I'm not sure this section really classifies as "terrain analysis" but I figured you guys would want to play around with bases instead of dirt and cliffs all day.  I'm nice like that.

Waypoints and Improved Pathfinding: Too Dumb To Drive
Remember how in the section about finding good mining beacons I said "if we do A* right we can also apply it to AI pathfinding"?  Well, that was more on an individual unit level.  This section is moslty concerned with the movement of large groups and planning ore-hauling routes if necessary.  In other words, we've got to get the AI to make use of waypoint plotting.  Luckily for us we've already gone and divided the map into sectors and bottlenecks, so we can use these to help us plot waypoints!

Here's just a rough idea of what I think the AI would do to issue group waypoints:
1) Set up a queue of waypoints.  It should start out completely empty.
2) Determine sector the group's destination is in.
3) Determine sector group is in. (Note that groups may take up more than 1 sector depending on their size; in this case go with whichever sector has more group units in it.)  Push this to our queue.
4) Check all bottlenecks leading out of this sector.  Don't store anything yet.
5) Check all bottlenecks leading out of this new sector (excluding the one we used to enter this sector).
6) Choose the bottleneck from step 5 that brings us closest to the target area.  Get the one from step 4 that gave us the one from step 5.  Push them both to the queue (in order step 4, then step 5).
7) Repeat until we get to the target location.
Issue move orders to all units in that group, making sure they go through each waypoint (and wait for the group to catch up at each stop?).

Again, this is blurring the lines between terrain stuff and unit stuff, but I don't think anybody will complain.

Also note that trucks will have to do a similar thing.

Identifying Good Base Locations: Nice neighborhood AND affordable!  Just watch out for those sub-prime mortgages...
Okay, so, what do you want when you build a base in a Land Rush?  Good ore, enough space for buildings, enemies not nearby, allies close (if applicable), and nice bottlenecks to make defense manageable, right?
So how can the AI determine all of these factors?  I see a few possible methods:
1) Search for large chunks of open land suitable for building, evaluate based on number of bottlenecks and quality/quantity of mines.  Such a system may favor building in the middle of the map.
2) Search for small, defendable bottlenecks, maximizing defendability.  Factor in amount of available land and mines.  This AI may favor small bases in corners and tight spaces.
3) Search for the best mines.  This is probably how most people play.

Really, we can judge locations based on whatever criteria we want, and we can have the factors influence the decision making process in any number of ways.  This is something we'll really want to discuss in detail before we start anything.



Okay, I need to take a break.  Start the discussion and I'll see you around.

Note: This was just pasted in from a text file I wrote in advance, so let me know if there are any weird formatting errors/etc.

[jcj94]

We need to think of criteria to look for when searching for bottlenecks. Here are some thoughts, please add your own:
-A "bottleneck" should be defined as a line with two sectors of open terrain on both sides. The line's endpoints must be impassible terrain. Should we require the terrain on one side to be bigger than the other (be funnel-shaped)?
-Should we limit the number of bottlenecks we can have in close proximity to each other? If so, based on what?
-Should there be boundaries (lower and/or upper limits) on the size of bottlenecks?
-Should we implement some kind of system to "rank" bottlenecks? How do we determine what makes one bottleneck "good" while another one "bad"?

I think we should attempt at making a bottle neck point based off of Distance between, what impassible is it (I believe 1/2, not sure if that makes much of a difference) OR how much of it is there, like a 4x4 block of a crater or a 2x9 block of a cliff-side.  Along with weather or not there is a LEDGE above it. That way it might be able to double defend against the ledge.

[evecolonycamander]

another point that the AI should be able to figure out is out ranging your enemy. i went stick vs. laser and was trashing the units just by staying RIGHT out of my opponents range

[jcj94]

And using unit damage blockades, if its plymouth and it has ESG and it has a bottleneck, then Start shooting mines a mile wide, it'd survive for a good while before  ALL ESG were gone!  (note: I have used this tactic in La Cor to push units back)

[Sirbomber]

I think I get what you're saying about the bottleneck definition JCJ, but could you maybe draw a picture or something?

As for the other points, they're all good ideas, but we're going to deal with that when we get to unit micromanagement.

[evecolonycamander]

he is explaining that the AI should use the land mine bottleneck strategy that makes passing a location impossible without well used EMP missiles. basically, shooting at the bottle neck with ESGS to make an impassable wall

[Sirbomber]

...Not what I meant ECC.  I was asking him about this:

I think we should attempt at making a bottle neck point based off of Distance between, what impassible is it (I believe 1/2, not sure if that makes much of a difference) OR how much of it is there, like a 4x4 block of a crater or a 2x9 block of a cliff-side. Along with weather or not there is a LEDGE above it. That way it might be able to double defend against the ledge.

[jcj94]

...Not what I meant ECC.  I was asking him about this:

I think we should attempt at making a bottle neck point based off of Distance between, what impassible is it (I believe 1/2, not sure if that makes much of a difference) OR how much of it is there, like a 4x4 block of a crater or a 2x9 block of a cliff-side. Along with weather or not there is a LEDGE above it. That way it might be able to double defend against the ledge.

For those I'm talking about the different terrain types, as in Fast Passible 1, Fast Passible 2, Cliff Side High, Cliff Side Low, Imassible 1, Impassible 2.  The AI could figure out if there is a small "cluster" of this, or if its a longer, more spread out "line" of it, based on dimensions, NOT TOTAL AREA (because 4x4 and a 2x8 would be the same)

Now I'm defending using this by, A human would know that terrain is imassible, not nesicarily what TYPE the mapper uses, but they would know "cliff" from "crater" by looking at them.


For the distance between, if there is a HUGE gap between impassible tiles, ignore it.

 

[Sirbomber]

Now I'm defending using this by, A human would know that terrain is imassible, not nesicarily what TYPE the mapper uses, but they would know "cliff" from "crater" by looking at them.

That's pretty much the only way we can do it, yeah.

For the distance between, if there is a HUGE gap between impassible tiles, ignore it.

In most cases this is what we'll want to do, but if there are no other alternatives the AI needs to know where to draw the line and bunker down.

[jcj94]

For the distance between, if there is a HUGE gap between impassible tiles, ignore it.

In most cases this is what we'll want to do, but if there are no other alternatives the AI needs to know where to draw the line and bunker down.

I can see this scenario clearly on something like the first mission form both story lines.  That is a HUGE area, but the bottleneck would be pointless to defend, and It wouldn't even (most likely) get attacked through it!  There are other maps, but that was just the first to came to mind, disregarding size restrictions here.
 

[Sirbomber]

Well, the fourth image I posted is from Plymouth Starship 1, and that basically stretches from one side of the map to the other.  The map has no bottlenecks between Eden's spawn point and your base.  Of course, volcanic eruptions will change the layout of the terrain and create a few bottlenecks.

Hmmm, speaking of, the AI should probably be able to re-evaluate the map in response to lava flows and Blight growth...

[jcj94]

And not just blight growth and lava growth but the possiblity of HAVING both of those features in the game.  More so it knowing disasters are enabled, and looking to see if its the "acient lava flow" tiles

[Sirbomber]

No, we're more interested in celltypes.  In most maps with inactive volcanoes, lava flow tiles are usually type M2 (the same as sand dune tiles).  If there are active volcanoes, they're either S1 and/or S2.  The AI should be cautious around these tile types, and if it detects an eruption, try to figure out where the lava can spread.  It should probably keep a copy of the original map from the start of the game (before or after unit placement) in memory, and then check lava flows to see what their celltype was originally.  If it discovers that a celltype is lava-possible, it should avoid building on tiles of that celltype if at all possible.  It should probably do this as infrequently as possible.

[jcj94]

I look at maps in.. a similar sense I guess.  

And another thing you might not have mentioned, cliff top defense.  If your up "higher", and the enemy has to snake around cliffs to get to your position.  Now most people would only spare a couple GP's (if any, more likely units are used) for defending that.  BUT If we have the bottleneck detection the AI might build GP after GP.  I was thinking about this when I looked at the Colosseum map.  So many "bottlenecks" but so few actually worth wile to defend.

As for the lower size limit on bottlenecks, don't have one.  I've see ECC take a whole army straight through a 1 X 3 gap and penetrate because of 1: Weapon range 2: armor and 3: I didn't think it was an important enough entrance to block off.  We don't want to have some "little" (depending on how little that turns out to be) problem that messes our poor little AI up because of something like that.

There should also be an anti-sneak attack.  I've noticed that I can set a lynx with lights off as a precession of units flows by, cliff-hugging as usual, and it doesn't get attacked.  Humans can use the territory against each-other if necessary.  Its another thing the AI has to watch out for, Large Open Space AT NIGHT. (note: I realize this might come later, but I found it easier to post this with somethings I've noticed)  A real person would go OMG UNIT ATTACK but the old AI, not seeing anything in its light patch, wouldn't touch it.  There are perfect examples in La Cor, where you can park an enemy fleet outside of the GP's light range.

[Sirbomber]

Unfortunately, the AI will probably have perfect awareness of all units on the map at all times, so night-time sneak attacks won't work on it.  I just don't know how we'd program it to "see" units in the dark.

I mean, the other possibility is it just ignores enemy units with the lights off, but that's kinda enforcing artificial stupidity.

One possible solution to "vision" would be it automatically becomes permanently aware of any units hiding in the darkness that gets close enough to its own units (in which case sneak attacks probably won't work anyways, unless we arbitrarily slow down its reaction time to such units, which is again enforcing artificial stupidity) and it has a small chance to randomly become aware of hidden units in other parts of the map based on the map size.  There have been a lot of times people try to sneak-attack me on AtW, and the only reason I see their units is:
1) I got really lucky and just scrolled by the right place at the right time.
2) It gets predictable after awhile.
But I'm not sure we want our AI's defense to be luck-based.

Anyways, yeah, not really important now.  Please concentrate on the subjects at hand, since I hope to begin working on them Friday and be done with them by the 15th (22nd at the latest).

[Hooman]

Pathfinding algorithms can be used to determine accessibility of an area, as well as the real distance to a mining beacon. Shortest path algorithms usually include the path length in the output, as well as a way of actually tracing out the path. If the distance to a location is "Infinite" (often a sentinel value in path finding algorithms) than it's inaccessible. The actual computed length can also be used to determine the real closest mine. An obvious choice to look at here is the A* algorithm.

It might not be very efficient to repeatedly compute paths to determine if a location is accessible though. Mind you, normally the accessibility of a location is only in question when you're trying to compute a path to that location, so it is very natural to use a path finding algorithm to compute this. Provided the algorithm can actually find a real path, and doesn't just try to get there by heading off in the general direction, and possibly following a ridge.


A conceptually simple way to determine accessibility though, would be to use a flood fill algorithm, (such as in Paint), to mark all mutually accessible tiles with a common value. Perhaps start at a player start location, or where a unit exists, and flood fill an array with the same dimensions of the map, based on passability. That will mark all tiles that are reachable from the given starting tile.

You can also easily extend the idea to handle cases where not all units, or perhaps not all players, belong to a mutually accessible region. Perhaps someone makes a space race level where two opponents are divided by a ridge, and hence can't mount direct attacks against each other. In that case you're interested in accessibility of a specific destination tile given a specific starting tile. This can be done by multiple flood fills, each assigning a unique marker value to each filled region. You'll probably want to mark regions using adjacency of similar passability (so continuous ridges are lumped together, rather than every cell of a continuous ridge being it's own region). An easy high level implementation of such an algorithm would be:
1) Initialize an accessibility array (say to all 0).
2) Scan array (say left to right, top to bottom) searching for a tile marked with 0.
  2a) Flood-Fill starting at that tile with the next available region id. (1, 2, 3, ...). Eventually the whole map will be marked with non-zero values. I've leaving out the details of the Flood-Fill part itself, but that can be google searched. I believe I saw a wikipedia article on it once.


There is of course the question of passible by what vehicle? GeoCons can move over fumaroles, while other vehicles can't. That might make an area accessible to GeoCons that is not accessible to other vehicles. Perhaps choose something like a lynx track type to mark accessibility with.


A tempting idea that doesn't quite work is to use cell types to define regions or reduce the movement rates associated cell types to simple true/false values, and adjacent cells with the same true/false bit mask can be combined into the same region. This doesn't quite accomplish the end goal though, in that mutually accessible regions will often be marked with different region ids. What you want is essentially a map overlay for passability of each track type, rather than an overlay grouping comming tile movement characteristics. It can be done, but a single overlay with lynx passability might be good enough for your purposes.


Also, if you are randomly placing units on a map, say for land rush, you can potentially restrict placement to a region of the level designer's choosing. Possibly use the region containing the most tiles to avoid starting someone on a ridge. It would be fairly easy to compute a region size as you're building the regions, or as a post processing step. Also, if you can hook blight and lava expansion, it should be fairly easy to keep the required data structure up to date. Just start new regions for blight and volcanic eruptions.


Oh, and if you can, please try to include a non-zero cost for unit turning. It's a little more accurate that way, and it prevents units looking dumb zigzagging their way across a map, and stopping every few tiles to adjust direction. (Assuming paths and unit movement are still tile restricted).


A passability grid might also help with finding bottlenecks. Perhaps find an edge of an impassible region, and compute it's distance to the edge of another impassible region, provided a straight line between the two encompasses at least one passible tile. You might filter such results based on the length of the line. If the line is too long, it's not really a bottleneck. Another criteria might be to filter results based on the size of the enclosed area, if there is an enclosed area. If it's too small, than forget about it, it's just some small corner, like where a ridge bends in a L-shape. You don't want to mark lots of tiny trianglur shaped regions as having bottlenecks. You would have to come up with some heuristic numbers for this. Perhaps an area at least the size to the square of the length of the line defining the bottleneck?

Also, I've noticed both in your images, and previously from looking at potential bottleneck places, that people seem to follow ridges to their "end" point, and matching it up with another ridge end point to define a bottleneck. This doesn't really catch all of them, but that seems to be the best case. Corners of ridges also work well as points of interest. Sometimes an end point or a corner point match up well with a flat wall, but I generally don't consider the distance between two flat walls to really be much of a bottleneck. I would avoid marking the place in between as a bottleneck, both because long corridors mean many similar "bottleneck" lines, and because the point where a corridor opens up is the better place to mark as a bottleneck, and that happens when at least one of it's walls either bends or ends (assuming parallel walls).

[Sirbomber]

Hooman's last post is a good example of the kind of discussion we need: not just ideas, but ways to implement those ideas.  Take notes people.

Good point about not making turning "free".  I think I had considered that at one point (Arklon probably brought it up first), but had forgotten about it before I got around to writing the first post.  Anyways, I get the nagging feeling I'm going to be the one who has to do the A* stuff, so I might pester you with more questions later.

I do have a quick question about flood-fill.  When you say "search by similar passability" you mean simply "passable/impassable", right?  Also, Since the I1/I2 tiletypes usually mean something specific on most maps (unreachable/obstacle) should we put all tiles of those celltypes into the same region?  Because maps like Rock Garden may end up with a few thousand regions if we count each rock as its own region.

[CK9]

some thoughts on the bottleneck issue (sorry if I'm repeating anything, I don't have a lot of time right now to read everything)

a bottleneck should have a few distance definitions, such as "no bigger than 'x' tiles wide" and "no closer than 'y' tiles to another access point to the same two areas" (this one will require some futher thoughts into how to get it to recognize the full areas)

I did see mention of the two impassible types.  I believe one is defined as one you can shoot over and the other you cannot.  Impassible items you can shoot over are generally small and not useful for a natural bottleneck.  However, they can be usefull to artificial ones.

[TH300]

Since my time is limited, I only did a quick read over everything without understanding every detail.

I thought that we can get a lot of information if we do a simple dijkstra search above the map and record everything interesting. This will automatically give us "real" distances (to wherever we start the search), we only record what is reachable and we can probably identify bottlenecks on the fly (no, I can't say how to do it, yet. But I could probably figure it out).


For finding base locations, we'll really have to do it differently depending on the type of base that we want to build. For starting bases I'd first look for ore beacons and than look at the terrain. The Dijkstra search that I mentioned above could easily find a set of ore beacons sorted by proximity. Terrain analysis could be done for the 5 closest beacons and a quality value could be calculated for each. Finally the ai will move and build at the location with the highest quality value.

For non-starting bases (especially military outposts) it could be a good idea to search for easily defendable terrain (bottlenecks around it).

One thing about bottlenecks that is probably important has already been mentioned, but I want that everyone understands it, so here is a picture:

The length of A's unit front is smaller than that of B's and hence B has an advantage.

But bottlenecks can also be mean and give you less of an advantage. If in the above bottleneck B choses to attack A, A won't have much of an advantage:


Both setups assume that neither party has access to the area around the bottleneck. If A has access, A could do something like this to make the match even:


Thats why we'll really have to differentiate between bottlenecks and even between its entries.

My time is over, so I hope that I could at least point you into the right direction. If you give me enough time, I may eventually tell you how to code it. But that needs serious time, like a few weeks.

And generally, I cannot do any real task within a week (until I reach holidays which will be in August). If thats the requirement, don't count on me.

[Hooman]

I do have a quick question about flood-fill. When you say "search by similar passability" you mean simply "passable/impassable", right?

Right.

Keep in mind that passability depends both on the cell type and the track type. Before I said a path finding algorithm typically takes a start tile and an end tile. In the case of Outpost 2, if you wanted perfect accuracy, you'd also need to include a track type. The track type affects both what is reachable, as well as the distance.


The decision to combine regions is fairly arbitrary. The main requirement for a passability overlay, is that if one tile is reachable from another tile, they have the same region value, and if they're not, then they have a different region value. If a tile is impassable, then it can never be a source tile. (An impassable tile might be clicked as a destination, but really, an impassable tile can't be the real final destination either). If you lump all impassable terrain into the same region, it won't change the behavior of determining if a location is reachable.

One possible argument for lumping adjacent impassable tiles together, but not distance impassable tiles, is the different regions might help an AI process large impassable objects, such as ridges, as if they were one entity. I'm not entirely sure how this information would be used, or why it would be used, but it's something to think about. Maybe if you included bounding box information you could use it to help optimize path finding.


Also, since a typical map only really has one play area, you can potentially lump all tiles into two regions. Those part of the main play area, and those that aren't (impassable tiles and ridge tops). This does limit application to maps like ones that currently exist though. You would not be able to support a map with two isolated regions, such as the possible isolated space race style I mentioned before. It would cut down on the overlay size though, since you can use a single bit per tile.

More general approaches might use more memory per tile to support a larger number of regions. I don't think using 4, 8 16, or 32 bits per tile is all that unreasonable. If you're using 32 bits per tile to mark the region number, then there is no way to exceed the number of possibilities even if every tile was part of a distinct region (which wouldn't be a very fun map to play on). At that point combining all impassable tiles into the same region is simply a matter of taste. There is no inherent overhead for having more regions once you've fixed the number of bits per tile to store region numbers. At least not unless you start storing additional region attributes, such as bounding boxes, which would be more useful if you didn't combine all impassable tiles into the same region.


I think I have a slight preference for combining adjacent impassable tiles into the same region, but not combining all impassable tiles into the same region. I think this would open up the most number of possibilities for using this information in potentially useful ways down the road.

Also, if you do combine adjacent impassable tiles into the same region like I'm suggesting, you probably want to use a slightly different definition of adjacency when doing a flood-fill. I would say don't travel diagonally when marking regions of impassibility, but do travel diagonally when marking passable regions. If you combine two regions of impassibility based on a diagonal link, then their union doesn't necesarily represent an impassable wall. Hence I think they should actually remain separate regions.


I should also point out there is a very high degree of similarity between Dijkstra's algorithm and A*. I would recommend using A* for gridded path finding over Dijkstra's algorithm though, since the distance heuristic can greatly reduce the area that needs to be searched to find a minimum path. Dijkstra's algorithm tends to expand out in a breadth first like manner, particularly on grid like structures with a fairly uniform edge weighting. The A* algorithm will search in the direction towards the target first (as predicted by the heuristic function), and only if the way is blocked will it end up expanding outwards in a breadth first like manner. Basically the heuristic function guides the algorithm by expanding paths towards the goal before trying paths that appear to lead away from it (but might get around an obstacle).

The efficiency of A* is controlled by the heuristic function which estimates distance remaining to target. The "correctness" of A* also depends on the heuristic function. A* will always find a path if one exists, but it might not be the shortest path depending on the heuristic. You can be guaranteed an optimal shortest path if the heuristic function is optimistic (is either correct, or predicts a shorter path than is actually found). Such a heuristic might be the cartesian distance (multiplied by the movement delay for the fastest terrain type). If the heuristic function overestimates distance remaining, then a non-shortest path can be returned. The increase in length of such a non-shortest path is however bounded, and depends on how good of an estimate the heuristic function gives. Using a modified heuristic may mean less area is searched, but slightly longer paths get returned. This may be desirable, in that slightly non-optimal output might be closer to what a human would discover, and also because less area being searched means less CPU time computing the path. I normally don't see A* used this way, but it's intriguing nonetheless. Note that a non-optimal path is found in this later case because once a path is found, A* will not keep looking for a shorter one if the heuristic predicts there isn't a shorter one (ie. it has overestimated the length of remaining paths). An interesting note is that if you fix the heuristic to always be 0, then you basically have Dijkstra's algorithm.

I would expect the area searched by A* to be less than Dijkstra's algorithm for a decent heuristic, such as cartesian distance. The area should be the same if you use a heuristic function that always returns 0. The area searched by A* will probably be more than Dijkstra's algorithm if you use a really bad heuristic function, such as one that predicts distance decreases as you actually get farther away. In that case it will search away from the goal before searching towards the goal. Such a bad heuristic would also likely return much longer paths than are possible.


If you're going to be reading about path finding algorithms than I have two general notes about them.
1) Shortest paths are not (in general) unique. Hence "a shortest path" is more correct phrasing than "the shortest path".
2) The problem of finding a shortest path has the "optimal substructure" property. This means the solution to a larger problem contains the solution to smaller problems within it. For instance, if we know a shortest path from A to B that goes through point C, then the sub-path from A to C of the path from A to B is a shortest path between A and C. (Same for the sub-path from C to B being a shortest path between C and B).

This second property is important to how path finding algorithms work, since they basically repeatedly extend a shortest path, one node at a time, to obtain shortest paths to nodes that are further away. An arbitrary extended path is not necessarily the shortest path to the new node, but the possibilities all involve shortest paths to adjacent nodes, so the possibilities are limited. Eventually the longer paths get overwritten by shorter paths as the algorithm iterates. The order in which paths are expanded to new nodes in an optimal algorithm is chosen so that a path isn't extended to a new node unless it is a shortest path to the current node.


I'm not sure how much that explanation makes sense right now, but hopefully it helps as you read about the algorithms. I can probably dig up some reading material in electronic form if you need it. I know I've got quite a few sources with diagrams to go along with the explanation. I don't remember what's good though.

[Arklon]

The problem with dividing the map up into "regions" of mutual accessibility is that the map changes. Structures, vehicles holding ground, Blight, lava, walls, or even code in the mission itself can cause areas that were once accessible from some point to be blocked off, or make areas that were once blocked off become accessible.

[TH300]

I want to re-explain the Dijkstra part of my last post, since Hooman misunderstood it. I am not saying, use Dijkstra to compute a path from A to B. A* is clearly better for that. My idea is to use the algorithm that Dijkstra uses to iterate over all tiles starting at A without a destination B. If done correctly this will provide us with proximity information for every tile that is visited. This means, the ai doesn't look for a mining beacon by taking its euklidian distance and then tests whether its really the closest; it instantly finds the closest beacon. It means that Dijkstra is executed only once where A* would be executed 10 times to compute each distance separately. (no, this isn't really the Dijkstra algorithm anymore. Its just part of it)

A similar (but different) approach would be influence maps. _A_ mentioned them once (don't remember in which context that was, and if she explained them in the same way as I will do now). For every mining beacon on the map the ai could compute the proximity of nearby tiles to that beacon (a number that is higher on tiles that are closer to the beacon). The sum is computed for every tile and the tile with the highest sum of proximities is a good base location, because it has the most beacons nearby.

[Sirbomber]

Okay, time to split up and get to work.
Who's willing to actually contribute?
Who's doing what?
I'll pick from whatever is left over.

[Hooman]

Ahh, right. Single-source shortest-paths, where a single call to the algorithm calculates the distance and shortest path to every node (tile), starting from the source. So, no early termination condition, or guiding metric function, which leaves plain old "Dijkstra's algorithm". Yes, that would make sense. Funny, because I was thinking of that difference in termination condition between A* and Dijkstra's algorithm when I started writing my post. They don't quite solve the same problem. At least not the standard textbook varieties. For some reason I assumed you meant the common modification to Dijkstra's algorithm that added a termination condition. In hindsight that's a bit of a silly assumption for the context.


Oh, and interesting comment about using Dijkstra's algorithm to find bottlenecks. I wonder if you could use the info from Dijkstra's algorithm to find bottlenecks by looking for path-lengths with an unusually small occurance. Such paths would probably be squeezing through a bottleneck, with a lot of the shorter paths ending at dead-ends, and longer paths sharing the shorter paths throught the bottleneck as common sub-paths. Mind you, I suspect that info gets increasingly useless as you move away from the starting point. Also, you might need to somehow group paths of similar length by common end point areas to properly handle places with more than one entrance.

Actually, that reminds me of a scanner I once wrote for Trade Wars. The game is played on an arbitrarily connected graph, where each node can have up to 6 links to other nodes (which were usually, but not always bi-directional). The same concept of finding bottlenecks for defense applied. I wrote a scanner to find all the dead end nodes so I'd know where to build up a planet. Eventually it got expanded to find strings of nodes leading to a dead end and measuring their depth so I could easily compare dead ends by the number of nodes protected by a given entrance node. Eventually the code got expanded again with some breadth-first search code to find possibly cyclic structures with a single entrance. This found a few triangularly connected dead ends that sometimes had even better depth. Finally it eventually got expanded to find structures with more than one entrance where the ratio of nodes in the cluster to the number of entrances was high. This was based on the number of nodes processed versus the number of nodes still waiting in the queue. As the edges were all uniform weight, the breadth-first search, and depth calculations made the code essentially equivalent to Dijkstra's algorithm, but with a maximum number of processed nodes set as an early termination condition. It seemed to work there, so I suppose it could work here.


As for actually doing any work, I don't think I can be depended on. I'm already chronically sleep deprived as it is, and that seems unlikely to change.
 

[evecolonycamander]

Okay, time to split up and get to work.
Who's willing to actually contribute?
Who's doing what?
I'll pick from whatever is left over.

I COULD get to working on a maze map to test path finding WHEN you guys get to that point. other then that though and im useless