Hiya

[Italian2007]

Hello, everyone!

My roommate and I were looking for a game to play together so we did some Googling and this game was mention on a long list of fun games to LAN. So after narrowing down the list we had about 5 games to select from so we started at the top of the list(AI Wars came first). Needless to say we never made it to the second game.

I digress! When i first got the demo for this game I tried out the first tutorial. The game seemed very overwhelming. I felt like I would never be able to figure this out. So i stopped playing and slept on it. The next day I came back decided to head first into a game and learn as i went. It was incredibly fun. I played for about two hours and was very happy that i managed to take 3 planets! So I was on the borderline if I should buy the game. So i went back to the ol' google machine and found these forums. After seeing x4000's support for this game I just had to support the cause (no offense keith didn't know about you until later ). The amount of time you put into this game, not just building it but the community, was superb. I was playing the game later that night with my roommate and decided i loved it so much I was buying the expansion.

Needless to say my roommate and i played a 120 planet game and we were kicking butt,well he was anyways, and we finally won! We are both so excited. It took two days and twelve hours but we did it! Then we go back to the main menu and i see the difficulty was set to 1(sandbox) q.q  I felt like such a noob.

Anyways my rant needs to come to an end.

TL;DR Love the game. Keep up the good work!

Ok now question time!

<Puts on CS glasses>

     When you select your units and move them via the Galaxy Map. Which algorithm do you use for shortest path? Is it Dijkstra's?

</glasses>

Also I like that there are cheat codes for this game, i am used to playing on xbox and not having codes so its nice to just use 'give me k' and get some knowledge at the start ^_^

I've told everyone i know about this game at least twice.

Ok I'm done for real this time.

[keith.lamothe]

Glad you're enjoying the game, thanks for the support

When you select your units and move them via the Galaxy Map. Which algorithm do you use for shortest path? Is it Dijkstra's?

Honestly I've been in and out of that code and didn't pay enough attention to know the mathematically basis of Chris's method there.  He developed a very sophisticated multi-layer approach for Alden Ridge that's much better than A* in that specific-domain.  I think the galaxy map one here is very similar to Dijkstra, since we lack a reliable heuristic to actually make it A* (and since Dijkstra is basically equivalent to A* where the heuristic always returns zero...).

[Italian2007]

Alright thanks, every time i pulled up the map it popped in my head, i can now rest easy.

[x4000]

Thanks so much for the kind words!

When I was working on Alden Ridge, I happened upon a website claiming that they had a far better pathfinding algorithm than A*.  They said it was based on the idea of how water flows, and basically was doing the pathfinnding in reverse, which had many benefits.  I had been knee-deep in A* and its many variants up until then, and while the claims of this little personal site seemed unlikely, looking at the code examples, and then profiling them... this guy was right!

And now I don't remember the site.  Gah.  I wish I could give credit.  I took what that guy was doing, which was itself sort of a variant of A*, and realized there were actually a number of other optimizations I could do at that time (such as solving 300 paths for the price of one, better diagonals handling, etc).  So I built all that stuff in, and then mine was even worlds better than the one from that other website, at least for the specific uses inside Alden Ridge.  I'm sure others have developed out similar things for other games (as I know most games have hybrid pathfinding systems), but this was unique in what I'd seen (as most of commercial pathfinding algorithms actually in use aren't shared).

So... with AI War's pathfinding for planets, it's a trivially easy problem, actually, compared to what I was doing in Alden Ridge.  I basically made a stripped down version of what I had been doing in AR, but based on arbitrary linkages rather than a fixed grid, and the result is what is here.

It's super simple, in concept:
1. Set all the distances on all planets to -1.
2. Set the distance on the target planet(s) to 0.
3. Now the loop: hang on to the index from the prior step, and all of the adjacent planets to that index get index +1.  Then increment the index and repeat.  Hang on to the number of distances that were set, and if that is ever 0, then end.
4. Now you've got the distances from every planet to the target planet(s) you're interested in, all in one go.

With diagonals and such it gets a bit more tricky, but that's how I'm able to do the "solve for everything in one pathfinding step," and it doesn't have any of the complexity of the A* algorithm.  Elegantly simple, and ridiculously fast and powerful.

[Lancefighter]

I.. dont suppose it would be possible to ignore a planet at any cost? for instance, in the last game I played someone had captured a grav drill, in a fairly high traffic area it seemed. Sure, going around would cost an extra hop, but it would avoid the grav drill effect.

So uh, can it be done that players can set an avoidance list?

[x4000]

That sort of thing would be possible, however it could also lead to large swaths of the map being completely inaccessible.  If that blocked-out planet is the sole entry point to the other parts of the map.  But otherwise, yes, that sort of thing is pretty simple on the backend, the main time is on the front-end interface coding (it's something we might consider in the future, in other words, but not in the short-term). 

We do that sort of filtered-routing already in some fashions for a lot of things for the AI and the humans, actually.  The pathing for players is actually more complex than I mentioned above, as it has several other layers on top of it: can I get to the target using just friendly/neutral planets, and what is the shortest path to any friendly planet that has a direct path back to the target.  In the case of the AIs, some of them aren't allowed to pass through player planets at some points, so they do pathing that ignores that.  On lower difficulties, for example, that is how you can wind up with "stranded" astro trains that are surrounded by player planets and thus aren't allowed to go anywhere.

So while the above algorithm is the basic underlying pathfinding logic, there's a lot more hybridization logic going on above it.  I'd forgotten some of that until you brought it up, I haven't really had to touch that in over a year.

[Lancefighter]

o.0 some astro trains cant travel to player planets on low diffs?


But well, i dont mean that it /completely/ removes a planet from all travel, just optimally paths around it, weighing it as 5 planets or something instead

[Echo35]

I.. dont suppose it would be possible to ignore a planet at any cost? for instance, in the last game I played someone had captured a grav drill, in a fairly high traffic area it seemed. Sure, going around would cost an extra hop, but it would avoid the grav drill effect.

So uh, can it be done that players can set an avoidance list?

Shift Click is your friend

I've had a number occasions where the fastest route was through an Ion Cannon Mk 4 system or something. Never auto path.

[x4000]

Yeah, on difficulty 5 and below (or maybe just below 5), astro trains are never allowed to enter player planets.

Regarding the optimization of paths, the only way to really do that is to calculate the pathing twice: first try it without going through that planet, then if that doesn't result in a valid path, try it again with the planet in the list.  Since this is a pretty tiny set of nodes (120 at most is miniscule for pathing), that's not really too much a worry.  As noted, it's mostly an interface thing, and just the time on that part and fine-tuning it.  But, as Echo says, pretty much shift-click is the way to go when you're in doubt.

[Lancefighter]

well, mostly my issue is that I'm too busy not paying attention to micro my paths :\
like my set of mk3 engineers - i often dont know (or, well, care most of the time) where they actually are, i just know i want them HERE, as soon as possible.

Unfortunately, when my ally has a grav drill with econ station on it that happens to be the quickest path.....

[keith.lamothe]

I could throw a "prefer to not go through this planet in auto-pathing" toggle on the per-planet controls window pretty quick (sync code and all), Chris, if it's something you wanted to do.  The power users would probably prefer an actual weight-setting mechanism (slider, probably, rather than textbox), though I think just going with the toggle for the first go would be better.

[x4000]

Oh, I hadn't thought of that.  Yeah, that page is so nice, it really simplifies a ton of things like this!  When there's a spare bit of time, we should do that.

[RCIX]

It's super simple, in concept:
1. Set all the distances on all planets to -1.
2. Set the distance on the target planet(s) to 0.
3. Now the loop: hang on to the index from the prior step, and all of the adjacent planets to that index get index +1.  Then increment the index and repeat.  Hang on to the number of distances that were set, and if that is ever 0, then end.
4. Now you've got the distances from every planet to the target planet(s) you're interested in, all in one go.

Holy cow! i think i did something very similar when writing a tool once (that needed to do graph based pathfinding similar to AI war's galaxy map, with the added issue of travel distance). I was gonna suggest it to you, but i never got around to it

[x4000]

Nice!  See, I figured it had occurred to others as well.  But not everything that occurs to many people gets actually published in books or on the Internet.  Surprising how many things are that way in programming.