AI/pathing request

Umm....not sure.  The pathfinding code uses an algorithm to weight all of the possible tiles to move to, and knowing that it would be quicker to go around the influence area of a Super Isolationist would require knowing something about the tiles around the tile that is currently being weighted.  If we had to check the tiles around every tile that was in isolationist space within a certain area, that could significantly slow down the pathfinding.  We may be able to fudge it by adding a constant value to any tile 'owned' by a Super Isolationist, the same way that we did for the asteroid fields, but with the asteroid fields we at least knew that there would be no more than 4 fields in a belt on a random map, so the fudge factor works reasonably well on a random map. 

If you send me an e-mail with a zipped save game wiith one or more ships parked just outside Super Isolationist influence, it will make it quicker for me to investigate.  Send it to [email protected]

 

 

I didn't have one handy, so I threw one together quick. Email sent.

When passing into an Asteroid field though, that'll stop you dead in your tracks that week, whereas a Super Isolationist aura will only recalc the max movement points upon a new week or after combat. So saying that, the two don't work exactly the same way, even though they have the same end result (slowed movement rate).

I have noticed it is much, much better to move my units myself rather than picking a distant point in space and right clicking. Unless I drag a line diagonally my units tend not to move diagonally, instead there are multiple times where it will move horizontally one space then vertically the next instead of taking a diagonal move. It can make all the difference when rushing a resource or planet.

It certainly doesn't happen all the time, but enough that I prefer to move the unit every turn if time is of the essence.

It's not the same issue you are mentioning, but something I thought I would bring up anyway.

The reasons I brought this up was due to having planets pop out ships and send them to a rally point. However, some of the planets were on the other side of some Yor territory. So my options were to either make a 'way point' rally point for them to reach first before moving on to the final spot, or remember which planets were the troublesome planets and manually move the ships ever time they completed.

Setup pre-war is also a reason, it just took a bit more micromanagement on my part to get the ships where I wanted them.

Any ship with an Auto-X though cause grief. Mining ships and survey/flagships blinding jump into that mess.

All-in-all I just need to pay more attention to my ships when a Super Isolationist is in the game. I had only asked if it could be done easily/timely. No sense in blowing a week of playing with the code just to automate one more portion of the game.

Interesting.

In old style games (going back to real oldies like Reach for the Stars) pathfinding was not a dynamic calculation. You just simply calculated the total distance and divided by the speed and that's how many turns the move took, no more no less. However movement was not displayed along the traveled path and in essence scheduling a fleet or ship for movement essentially placed it in "hyperspace" for the calculated duration of turns making the ship/fleet unavailable until it "popped" back into existence at the destination in the appropriate turn.

Certainly having to display the ship/fleet over the course of its path and allowing for the possibility that the ship/fleets destination may change at each turn while also having to account for moving obstacles (i.e. other ships) makes the pathfinding problem far more difficult.

While I understand the increased difficulty that this kind of dynamic pathfinding entails I have also been frustrated by the inefficiencies of the current code that can result in causing an autopilot path to take an extra turn over the path a human can take.

However, one of the biggest source of “extra” moves that I see occur in the game result from something that I would think could be fixed, although how easy such a fix would be I have no clue.

When setting a course from a source to a destination in a Cartesian plane (assuming that the motion is not directly along one of the two main axes or the diagonal formed by these axes) the minimum course is contained within an envelope that is bounded by two different paths. One path is to first take the direct horizontal or vertical path and then take a direct diagonal path from the source to the destination. The other path is to first take the diagonal path followed by the horizontal/vertical path. These two paths form a parallelogram with the source and destination at opposite corners of the parallelogram. Any path that is contained within this parallelogram will also be a minimum path course as long as you always go towards the destination. This isn’t really a mathematical definition of a minimum path but I’m sure you get the picture.

The problem with pathfinding as I see it is that it tends to take one of the two outer boundaries of the parallelogram as its basic course and then deviates from it as it encounters an obstacle. The issue is that since the course is one of the outside borders of the bounds on a minimum path it often occurs that when an obstacle is encountered a detour must be taken that lengthens the total path. However if instead of insisting on traveling the boundary of the parallelogram, a path is negotiated more down the center axis of the parallelogram then there is much more freedom to negotiate around an obstacle without increasing it’s path length. Of course this results in a path that is less “smooth” to follow but it does result in greater likelihood that the ship/fleet arrives at the destination in the minimum time i.e. the same turn a human would get there.

Another possible algorithm to use is illustrated by the following example. Let’s say an autopilot path is selected from a source to a destination. Let’s also stipulate that the destination is to the left and down of the source and that the destination is further to the left of the source than it is down from the source. In this case the minimum path is any course that goes from source to destination that uses any combination of moves directly to the left or diagonally downward to the left. Movement in any of the other six possible directions results in an increase of the path length and should be avoided. Now given that most obstacles are simple one point obstructions then calculating a path three parsecs in advance will avoid most of the “extra” moves that I see the autopilot take. Clearly if multiple objects form a barrier then this won’t necessarily work, but most of the time I see the autopilot take extra moves is because it happens to choose the “wrong” way to go around a single point static object like a planet.

One thing that happens to me is nonautomatic mining ships not starting to mine when I actually send them to the asteroid field. They will just park on the field and not start to mine. I get around it by stopping just short of the fields and then manually moving the ship. Works fine if I remember to check them. But I do tend to forget to do that. Would it be difficult to fix this?

If you could find a situation where this is repeatable (ie. you can always get to the destination in less moves manually than on autopilot from the same starting point), then please make a savegame, take a screenshot, and tell us who to move to where.  Zip up the save and send it to [email protected] with a description so we can investigate.

Thanks,
~C

How did you make out on this? If it was too much a PITA I would understand.

I don't have a save anymore, but any case of 'cluttered space" tends to produce this -- try playing on a "tiny" map with lots of habitable planets in the center. Things become a HUGE mess, and manual pathfinding is essential to sanity. (Edit: Not something you can really fix, since a lot of pathfinding through that mess revolves around knowing when to wait for the stupid freighter to move out of the way and the like).

That and also I had a ship go around a parsec that on the previous turn had an anomaly. The pathing didn't update itself that following turn and tried to continue on it's previous flight plan around the object.

So it seems to be an issue with non-static items (ships/anomalies).

I've also seen ships take bad paths because of starbases -- if they'd detoured earlier they could have avoided any delay, but because they waited until they were right on TOP of the starbase, there was an (unnecessary) delay. Its like the don't consider what enemy units might -- or might not -- be in the way.

Hrm...makes sense since they can occupy the space as one of their own starbases...

Me personally, I'd love to go back to the old style where the ships just bounce to where you wanted to go without showing exactly how they got there.

There are a few reasons for this.

1) the current animation is pretty slow in moving the ships.
2) the algorithm currently is faulty. (as mumble was pointing out)
3) ships flying past each other shouldn't be a big deal. (it is space, and you could say they detoured over/below)
4) hugely simplify processing hit of the current algorithm.

Lastly, I think 1 other thing could be done that would make the game more interesting. That is each course change should use an additional move. That would reward you for setting a long autopilot, and deter you from moving 1 click at a time. This would cut down on 30 move ships from being able to desimate 30 other ships. It would add an interesting dynamic to the game, get there quicker but without knowing whats there, or turtle there so that if you need to turn around you can.

Personally, the asteriod pathfinding should be throw away. There's never a reason to fly into an asteriod field. (unless you ship moves at 1, lol). You lose this turns moves, and the next. It drives me insane when my ships fly into asterioid fields...

Simple ability to give ship waypoints imho would be simpler to implement, more versatile and hence better. I get annoyed by constant need to micro my scouts and radar ships on every turn - just because I cant give a path different from straight line

This idea would kill the game for me.

Why? Because if ships just popped up at their destination, you would have to heavily defend all your planets because you would never know if an invading fleet was on it's way. Your defensive fleets would just be simple to bypass.

Your description makes it sound like you are not using A* for pathfinding. If you did (or do?), the check could be in the heuristic.

I meant at the end of each turn pop in... Which would still mean the game would have to figure out where they should go. (but it could do it purely mathametically, unless the landing spot was occupied, then it would have to look back to see where best to drop you.)