Two bug reports

[Douglas]

1) The pathfinder is not actually a path finder, but a path guesser. Way too many times, I've had it ignore obvious mag tube routes, sometimes even when the mag tube is an utterly trivial single square deviation from the direct line path. I've even had it go off the mag tubes for a single square, only to move right back on one square later, when there's another mag tube square connecting them without even requiring a greater number of steps. Worst of all, I've had a unit repeatedly move back and forth between the same two squares until it ran out of movement, never actually getting closer to the destination!

On top of this, it doesn't check for zone of control restrictions, and gets stuck, unable to execute a goto order, when it reaches a point where the next step it tries to take is blocked by ZoC.

I'm using Thinker, and through it scient's patch, so scient and Induktio please fix it to be an actual pathfinder. And while you're at it, make it stop cancelling the goto when it gets adjacent to an enemy unit that was already known about and accounted for when the order was given. You could also remove the prompt for continuing to move after a few dozen steps, which I think was put in as a crude patch for the problem of infinite cyclic movement, which only happens in the first place because the game doesn't have a proper pathfinder.

2) If a former's current order somehow becomes already-completed without the order being cleared, the former spends its entire turn just to figure out that its job is done. One way this can happen is for a forest to expand into a square where a former was either planting forest or clearing fungus. It could also happen when a fungal bloom hits a square where a former was planting fungus, though I imagine that's a rather rare occurrence. There's also a much more common way that doesn't involve random chance - the combination farm+X+road convenience commands. Completing the last order in the combination clears only the single-job order, not the combination, and the next turn is then wasted on discovering that the combo is done. This happens even for solo formers, as well as groups.

Please fix this so that a former with an already-completed order just clears the order without spending movement. It would also be nice to have farm+mirror+road and farm+condenser+road commands, and a way to add soil enricher and/or mag tube to the combo, but that would be an extra feature, not a bug fix.

[bvanevery]

Notice the lovely selectable BUGS icon next to my reply title.  So pretty!  And So Can You.

Are you sure you know the difficulty of what you request?  It's not like either of these guys are original developers of the game with well commented source code in front of them.  There's a binary blob that they have to go in and edit, in assembly code.  If somebody has discovered and decompiled the pathfinding code, then maybe it's fixable, and I don't know if historically anyone has done that.  If they haven't, you're talking about a problem that's somewhere between horrifically difficult and impossible.

Path guessing would be a perfectly good paradigm in a game that ran military conflict that way.  Not knowing the local lay of the land, and the locals having a defense advantage that way, is a real thing that happens in war.  I seem to remember that when Ronald Reagan invaded Grenada, I think the military had to get maps at local shops!

Now of course, SMAC builds the expectation from the get-go that your pathfinding is supposed to work.  So failing to deliver on that, is a bug.  It's especially bad with Formers in the presence of a political boundary, i.e. friendly vs. enemy territory.  The pathfinding for Formers behaves as though that matters, when it clearly shouldn't.  Where you end your turn is consequential in terms of the game rules, not where you're moving during your turn.  Yep, it's a horrible PITA and has caused me to lose Formers when trying to use them as front line siege weapons.  You curse the game for a bit, then you start remembering to move everything manually and tediously, until you're back in friendly territory.

I have my doubts that fine tuned selection of "don't stop for these particular units" is even possible in the game's original code.  It's not the sort of selectivity that I would have expected the game to implement.  You can turn on and off who you stop for, in your player options.  It might be tedious for you if you want it multiple ways, but you may find it best to just turn the stops "off" and leave it like that.

You won't question the expediency of a loop breaking routine, when you've seen how often it can come up in certain styles of play!  Big maps and crossing some kind of map boundry, really throws things out of whack.  I suspect the wraparound logic, and also bottlenecks moving from one land mass to another across a diagonal.  Realize further that you cannot predict when there's going to be a bug in this game, or any game for that matter.  The loop breaking routine is a safeguard that keeps you from having a crashed and unrecoverable game.  I suggest you get used to it and be thankful for it, however crappy the game's pathfinding may seem to be.  Even if Induktio or Scient made it "seemingly perfect", it would only be a matter of time before someone discovered a new way to break it.

The Formers do have some broken "orders" behavior.  It hasn't bugged me enough to deeply irritate me, but I have noticed the occasional goofs.  I terraform every single square of the game by hand, and I never use "combo" orders.  Anything you queue up for later execution, in any game, is going to be invalidated by changing circumstances.  So I don't do it in the 1st place.

Have you looked at whether Yitzi's or Scient's patch already lists the Former thing as fixed or dealt with?  There are some lists of bugs on the wiki, of what these patches supposedly address.  Of course the downside in the case of Yitzi's patch is one would have to spend time rediscovering what / how he did things, as he's not around anymore.  But knowing that someone fixed something proximate to this, gives a pretty good indication of the viability.  Whether the trail is warm and just needs elbow grease to figure out, or whether it's a "cold hunt" through the code to find out what's wrong.

I suspect that Yitzi's bug fixing was primarily opportunistic, and not driven by any particular vision or triage of what was important to fix.  I think as he tooled around in the binary, he found stuff he was capable of fixing, so he did so.  Whatever he happened to turn up.  As a planned list of game improvements, his patch leaves much to be desired, which is a main reason I don't use it.  The other being that he didn't do anything to improve AI performance, which to me is the single most glaringly important thing to fix about the game.  Not knocking what he did do, as he clearly did a lot of work, but I think when people say "patch" they start having a lot of magical expectations about what kind of development work was done.  Yitzi did what he did, no more and no less.

[Douglas]

I certainly don't expect it to be trivial, but I doubt it's as difficult as you seem to think. Yes, in general modifying the exe is hard. I've gathered from reading some things on this forum that redirecting a function call is easy, however, even if the new destination is in an entirely separate file, and that's about the level of binary hacking I'd expect to be needed.

I expect that, somewhere in the game binary, there's a function that takes a unit and destination and returns a path. I think fixing the pathfinder could be done by writing up a correct pathfinding function in regular source code, compiling it, inserting the compiled function into the exe, finding the original pathfinding function, and redirecting it to the new one. I think the trickiest parts would be a) finding the original pathfinding function, b) accessing and correctly interpreting the necessary game data, and c) matching the expected binary format for the returned path.

I don't know how tricky finding the original function is, or determining the expected path format. The existence of Thinker pretty conclusively demonstrates that accessing and interpreting game data is a solved problem, however, and I could write a correct pathfinding function myself in minutes.

Not stopping for already-known units might be more complicated, true, but it also might be relatively simple. I don't have enough information to assess that.

Getting rid of the loop break doesn't really have to be getting rid of it - just increasing the number of steps before it kicks in would be enough. I haven't tried to pinpoint the current limit, but it's somewhere around 30, and I'd guess 32. I've been finding myself quite routinely giving goto orders for around 40 mag tube steps, so I trigger it a lot for perfectly legitimate non-looping movements. Increase it to 256, and I'm not sure I'd ever reach that except in a genuine infinite loop, but it would still stop infinite loops in a reasonable amount of time. That's probably a single byte change, just have to find where the maximum number of goto steps is stored.

Neither Yitzi's nor scient's patch mentions formers in the fixes list.

[bvanevery]

and I could write a correct pathfinding function myself in minutes.

You should then!  Nothing like a pull request for getting what you actually want out of Open Source.

And you should test it.  Which will not take "minutes".

Increase it to 256, and I'm not sure I'd ever reach that except in a genuine infinite loop,

But what about players who aren't you who think their game is freezing up?  It's all about how long such things go on. 

[Douglas]

and I could write a correct pathfinding function myself in minutes.

You should then!  Nothing like a pull request for getting what you actually want out of Open Source.

And you should test it.  Which will not take "minutes".

I'd need to have ways to access the relevant game data provided for me, which... now that I think about it, Thinker mod might actually have publicly available. OpenSMACX might even have the hooks needed to make it be used, but I'm not sure how far along it is. In either case, I'd need to familiarize myself with the existing code first. I'll consider it.

Increase it to 256, and I'm not sure I'd ever reach that except in a genuine infinite loop,

But what about players who aren't you who think their game is freezing up?  It's all about how long such things go on.

If it's an actual long distance trip, then the player should see the unit rapidly blinking along the mag tubes, periodically interrupted by the map getting recentered to keep it in view. If it's a loop, 256 mag tube moves without recentering the map would take a few seconds at most, and then the prompt would pop up. Even for players with the "move units with orders quickly" option turned off, I just checked and goto movement on mag tubes is still just as fast. No other movement mode is relevant because mag tubes are the only way to reach even the current limit for that prompt.

[Induktio]

1) The pathfinder is not actually a path finder, but a path guesser. Way too many times, I've had it ignore obvious mag tube routes, sometimes even when the mag tube is an utterly trivial single square deviation from the direct line path. I've even had it go off the mag tubes for a single square, only to move right back on one square later, when there's another mag tube square connecting them without even requiring a greater number of steps. Worst of all, I've had a unit repeatedly move back and forth between the same two squares until it ran out of movement, never actually getting closer to the destination!

On top of this, it doesn't check for zone of control restrictions, and gets stuck, unable to execute a goto order, when it reaches a point where the next step it tries to take is blocked by ZoC.

Okay, let's chime in on this...

The last time I inspected the pathfinding code was when I was evaluating implementing a feature that would deny the use of roads on enemy terrain (attackers must pay full movement costs on enemy terrain). I did not implement that feature at the time, but it could have been done by modifying a function called hex_cost that is used by pathfinding loop to determine how many road movement points a particular square consumes, e.g. a regular road is 1 points, flat terrain 3 points.

That would probably be the easiest way to modify pathfinding but going beyond that might get a little bit tricky because pathfinding interacts in a very complex way with the global game state. Most of the pathfinding routines are closely associated with some C++ class structure produced by the compiler, so then one would have to pass around some arbitrary this-pointers while calling such functions. Not saying it can't be done, but it would require quite a lot of reversing work to get done and then even more testing. One of the problems produced by the game design is that ZoCs are absolute, they block all normal movement, unlike in some later Civ games. For the AI it would be much easier if it could move anyway, but maybe taking a little bit of damage for passing an enemy ZoC.

[bvanevery]

For the AI it would be much easier if it could move anyway, but maybe taking a little bit of damage for passing an enemy ZoC.

From a game design standpoint I predict that to be a complete fail, at least in this game.  "Formers getting themselves killed" is a typical problem of many Civ-style games.  Allowing units to continue to move while taking wounds, is likely to be a quick death in many circumstances.  If you think you can work "throttling code" into such a decision, have fun with that... but game design-wise I think you'll be walking into a genre of AI misbehavior that players do not want to see in their games.

Civ III had the play mechanic of slowing down enemy moves if they entered the home territory of another player.  Personally I think it is an irrational and stupid mechanic from a simulation standpoint.  Like why should Patton or Rommel be stopped cold by anything, if they have the tanks and the fuel?  From a gameplay standpoint, one could debate the merits or demerits, as a pure conceptual system.

Making it more expensive to move through an enemy zone of control, is a related but not identical game design idea.  Seems like it could be a feasible pathfinding system to implement, and isn't entirely unrealistic.

[scient]

It looks like there is a Path class devoted just to path finding. I've tagged it in my notes to complete for 0.3 release. I'm nearing 0.2 release with 300 functions redirected to DLL. One of them is the hex_cost function, mainly to fix a bug with Sea Lurkers.

[scient]

Also, I don't recall ever patching terraforming code in that way. I'm not certain off hand how to fix this issue. There are some core terraforming functions I haven't worked on yet. Maybe some kind of check/refresh when square/map gets modified. I've added it into my bug tracking notes for future reference.

[Douglas]

Also, I don't recall ever patching terraforming code in that way. I'm not certain off hand how to fix this issue. There are some core terraforming functions I haven't worked on yet. Maybe some kind of check/refresh when square/map gets modified. I've added it into my bug tracking notes for future reference.

It could also be fixed in order resolution - when a former attempts to do something that's already done, skip consuming movement, and only clear the order. Or... this is speculation, but I'm guessing that resolving a former order is done by first doing the work and then checking whether it's done. If so then this could be fixed by invoking the check both before and after the work, instead of only after.

[scient]

Yeah, there are some "upkeep" functions that kick off during start of Players turn. One of which I believe is handling terraforming and updating progress. This would probably be a good place for fix where it handles resolution better. I'll definitely look into it more when I delve into that code. I've only done some sub functions related to terraforming so I have a murky idea of game logic.

On another note, I skimmed through all Path class functions and it looks like I've done most of sub-functions it calls already. Or have planned to do in next release (Map related code). I only saw 1-2 instances of some class stuff related to MapWin that I hadn't planned on doing prior.

[Douglas]

From observations while playing the game, terraforming progress is definitely done during the player's turn, piecemeal, at the point when each former would otherwise become the active unit and ask for orders. It works the same as any other multi-turn order, such as a long goto without mag tubes. Once upkeep is done, and each time the player gives a turn-ending order, the game picks a unit to process next. If it has no orders, it gets activated, blinking and waiting for orders. If it does have an existing order, that order is executed, and if it has movement left after completing it then it gets activated.

Hmm, after typing all of that, I suspect the point that needs to be changed may be part of general order execution, not something specific to formers.

[scient]

Without derailing myself with shinny object syndrome, I think there are two instances of terraforming process. One, during player turn (initiated by Player or AI). I've actually broken down some of these functions related to Veh (unit) code. Ex. veh_wake when you click on a terraforming that's already doing work. The other is handled during turn upkeep. A quick way of finding code locations is looking at references to Veh.terraformingTurns.

[Douglas]

• I order a former to build a road that will take 2 turns.
• I end turn.
• On the next turn, I check the former. It has movement available and the road is not finished.
  
  • I go through all other units, playing the turn. At some point, the former changes to already moved, and the road is done, without me personally interacting with it.
  • or, I order another former to help it finish. The road immediately completes, and the first former activates, ready for orders with all movement available.

The combination orders work similarly when all parts are done - at some point during the turn, the former clears its order and skips its turn. If I cancel the order before that happens, I can move the former or give it another order as if the cancelled order had never been there. If I wait to after that point, it's too late and the former's turn is wasted.

[PvtHudson]

1) ... Way too many times, I've had it ignore obvious mag tube routes, sometimes even when the mag tube is an utterly trivial single square deviation from the direct line path. I've even had it go off the mag tubes for a single square, only to move right back on one square later, when there's another mag tube square connecting them without even requiring a greater number of steps...

To my knowledge, this behavior occurs when underlying road is destroyed, rendering intact magtube unusable. Hope this helps.

Much more sad behavior demonstrate needlejets, flying aimlessly back and forth, sometime crashing in process.