1/* %W% %G% %U% - (c) Copyright 1987, 1988 Chuck Simmons */ 2 3/* 4 * Copyright (C) 1987, 1988 Chuck Simmons 5 * 6 * See the file COPYING, distributed with empire, for restriction 7 * and warranty information. 8 */ 9 10(Notes tagged with ESR describe Eric S. Raymond's changes) 11 12Bugs 13---- 14 151) The computer is allowed to leave armies in cities. Fixing this 16feature might be difficult. This feature also gives the computer 17a small advantage which slightly helps overcome the natural superiority 18of humans. 19 202) Once upon a time, if a fighter landed on a carrier, the user 21was never asked if she wanted to move it again. I don't know if 22this bug still exists. 23 243) Satellites are not completely implemented. When the user 25moves to a satellite, it should be allowed. The user should 26not be asked if she "really wants to attack her own piece". 27Enemy satelites should not cause the user's pieces to be 28awoken, since there is nothing the user can do. 29 304) If the computer has a damaged ship and is returning it to 31port, the user can block the ship with another piece. The computer 32will not attempt to move the damaged ship. The user can then 33sail up a transport to the city the damaged ship is heading toward, 34unblock the damaged ship, and as soon as the damaged ship enters 35port, take the city. Since ships in port are capturable, the user 36should now own one slightly damaged ship. 37 385) Currently, a fighter's range is not decremented if it is not 39moved during a turn. This could be called a feature, but I think 40I would really prefer that a fighter's range was decremented by at 41least one each turn. The computer does not take advantage of this 42bug. 43 446) Movement of armies in "attack" mode seems a little strange. 45 467) Maybe in "sentry" mode, an army should wake up and go into "attack" 47mode if an invader appears on the continent. In any event, there 48should be some mechanism to allow a user to specify that an army 49should sit on the shore and wait for either a transport to pass by, 50or for an invader to appear on the continent. 51 528) When setting a city function, the computer should prompt 53for the various pieces of input. Even I have a hard time setting 54functions for cities. 55 56 57Code Cleanup 58------------ 59 601) The width and height of the map should be parameters to the 61program. Storage for the various data structures should be allocated 62dynamically instead of being stored in static tables. 63 642) Interrupts should be caught. When an interrupt is received, 65the user should be asked if she really wants to quit, and she 66should be warned if the game will not be saved. 67 68Performance Tuning 69------------------ 70 711) 'vmap_cont' and 'vmap_mark_up_cont' would almost certainly be 72faster if we didn't recurse, but instead used something like the 73perimeter lists used in all the other map scanning algorithms. 74Since 'vmap_mark_up_cont' takes about 10% of the processing time, 75the performance improvements could be significant. 76 772) The real speed killer is 'expand_perimeter'. This routine 78is very generalized, and not all the generality is always needed. 79It might be better to write multiple non-general routines. I believe 80this routine accounts for roughly 20% to 30% of the processing time. 81If we take subroutines like 'strchr' and 'terrain_type' into account 82as well, this routine accounts for more like 50% of the processing. 83However, on a mainframe, the game plays sufficiently fast. 84 85ESR: I've done some tuning of expand_perimeter. Further performance 86tuning is hardly an issue at this point. Modern machines are *fast*. 87The above has been preserved as a historical note :-). 88 89 90Debugging Aids 91-------------- 92 931) My current debugging algorithm is to put the program into 94debug mode with the "++" command, and then put the program into 95movie mode with the "%" command. When I see something wrong, I 96hit the interrupt key and restart the program, so that I can 97use other debugging commands. It would be nice if this interface 98was better. (See comments above about catching interrupts.) 99 1002) It would be nice if there were debugging commands which allowed 101me to examine the computer map and request information such as 102"What is this city producing? What objects are in this city? etc." 103This would be very much like the edit mode "?" command. 104 105 106Computer Algorithm Enhancements 107------------------------------- 108 1091) What improvements can be made to speed up the acquiring of 110territory by the computer? 111 112Note: As a person, I can acquire about 1/2 the board (and control 1133/4 of the board) in about 150 turns. 114The current algorithm seems to be a little bit slower, but within 115the same order of magnitude. 116 117Observations: 118 119I've implemented an algorithm which keeps the computer from exploring 120every little square of the world it comes across. Building satellites 121seems to slow down the computer. The computer has an algorithm 122for unloading armies on interesting continents. 123 124A careful balance seems to be needed between the number of army 125producing cities and the number of tt producing cities. Currently, 126I build a tt as soon as poosible. On large 127continents, this is a drawback, as the tt is built before armies 128are ready to leave. To counter this effect, I attempted to build 129more armies in other cities. This causes an overproduction in 130armies after the first tt's fill up and head off to find something 131to dump on. 132 133Suggestions: 134 135Various minor improvements might be made in causing tt's to load 136one or two turns faster, and to unload one or two turns faster. 137Other improvements would prevent two tt's from heading to the 138same destination. 139 140This fix would probably go in 'transport_move' in 'compmove.c'. 141In this routine, for a loading transport, we would count the 142number of adjacent loading armies for the current cell, for each reachable 143cell that is one away, and for each reachable cell that is two away. 144If there were reachable loading armies, we would move the transport 145to that square. Otherwise we would use the current algorithm to 146find a destination for the transport and move the transport to that 147destination. 148 149For unloading transports, things are perhaps slightly more difficult. 150I think what needs to be done here is, if the transport cannot move 151along a shortest path towards the destination, then the transport 152should attempt to move to an adjacent square which minimizes either 153the row distance between the tt and the objective, or the column 154distance between the tt and the objective. For tie-breakers, the 155tt would move to the cell which touched the most land. 156 157Possibly I should describe the problems that the above to tweaks 158would fix. For loading armies, loading transports prefer moving to 159staying in place. Thus, they will sometimes move from a square 160that touches lots of loading armies, to a square that touches very 161few loading armies. This probably increases the load time by one 162or two turns. 163 164For unloading tt's, a tt will often be on a diagonal from a city 165that is an objective. Unloading armies will hop off one at a time 166because there is only one land square on a shortest path between the 167tt and the city. This particular case wastes about 4 moves. 168 1692) The computer's algorithm is optimized for 70% water and 170a smoothness of 5. (More accurately, I developed the algorithm 171using these parameters for all of my testing and debugging.) 172Potentially the computer algorithm will be extremely poor for 173other parameter values. For example, the computer currently 174builds transports at the first possible opportunity. Transports 175would not be very useful on a world with only 10% water. (Still, 176there are checks to prevent ships from being built in inappropriate 177cities, so this may not be too much of a problem.) 178 179Potentially, the computer should use a more dynamic algorithm 180where it "notices" that certain kinds of pieces are going to be 181need in the near future and then builds these things. I've no ideas 182in this area for concrete algorithms, however. 183 184A plausible alternative would be for the computer to examine the 185parameters supplied by the user. If the user knows the parameters, 186why shouldn't the computer? 187 1883) The computer should be willing to land a fighter on a 189carrier if the carrier can be reached in one turn. 190 1914) The computer should "track" user ships. That is, whenever the 192computer sees a user ship, it should keep a list of possible locations 193where that ship could be. It should then make some attempt to find 194and destroy the ship. (See "Search and Destroy" under the user 195interface comments.) 196 197This code may be more trouble then its worth. Currently, it appears 198that the computer does a very good job of destroying user shipping. 199The reason for this is that there are good reasons for the user's 200ships to reappear where ships were previously seen. Also, the 201computer tends to amass great amounts of fire power when a ship 202has been seen, so the computer tends to bump into any other user 203ship that happens to be in the area. Also, the user is looking for 204the computer's ships, and is moving lots of ships into the sealanes 205that the computer tends to use. 206 207 208User Interface Enhancements 209--------------------------- 210 2111) In edit mode, it would be nice if it was easier to move around 212the screen. (Mouse based approaches where the user points and clicks 213to say "move this piece to here" would be real nice.) One idea 214would be to allow the user to type in four digits that specify the 215square to move to; or to type in two digits where the first digit 216is the 10's row, and the second digit is the 10's column. (Thus, 217if the user typed "43", the cursor would be moved to location "4030".) 218 2192) Small screens should not be redrawn so often. When moving 220pieces, we should move everything that is on the current screen 221(except for stuff that is real close to the edge of the screen, 222but not the edge of the board). If necessary, we might redraw 223the screen as the user moved off the screen. Or we could allow 224the user to explicitly tell us to redraw a new sector. If the 225screen was redrawn, we would then work on moving pieces that were 226displayed on the new screen. In general, we only want to redraw 227the screen if we absolutely have to. (This approach would also 228be real, real useful on terminals that are just a little bit smaller 229than the complete map. Using a terminal with something like 105 230columns will be extremely disconcerting. The screen will be 231redrawn for what seems like no reason at all.) 232 2333) It is extremely difficult to tell when a satellite has gone 234by, and when an enemy piece displayed on the screen is current, 235and when the piece is a ghost. 236 237One possibility would be to highlight enemy pieces that have just 238been seen. Another possibility would be for the user to type 239a "?" when the cursor is on top of any enemy piece, and the displayed 240information would be how long ago that piece was seen. (Also, see 241search and destroy tracking below.) 242 2434) The user should be allowed to "zoom in" and "zoom out". Zooming 244in causes the playing board to be printed at four times the density 245of the previous display density. Thus, four squares would be 246drawn as a single square on the screen. Zooming out undoes the 247affects of zooming in. Actually, there should be multiple 248levels of zooming; 10 levels would probably more than suffice. 249This enhancement allows the user to easily get a big picture of what 250is going on. Most of the time, the user would be able to play 251with the board zoomed in. The user might sometimes need to zoom 252out to navigate a ship through a "river" or an army over an isthmus. 253 254Currently, there is a command to display a "zoomed" version of the 255map. This command prints a compact display of the map that fits on 256the screen. This is not quite the same as the above, because what 257I'm suggesting is that the user be allowed to make moves on a compact 258display of the map. 259 2605) Search and Destroy. Here is an idea for a sizeable modification 261to the user interface. 262 263Basically, we want the computer to keep track of some information 264for the user. The information is possible locations of enemy ships. 265When the user sees a ship on the screen, the computer would start 266tracking the ship. 267 268(Tracking would be implemented as follows: The initial location 269of the ship would be stored in a perimeter list. On each round, 270the perimeter list would be expanded to encompass all cells which 271the ship could have reached. Cells that the user has seen this 272turn are removed from the perimeter list. After the user's turn, 273cells that the user has seen are removed from the list again. 274Problems arise when a tracked ship moves into unexplored territory.) 275 276Now the user should be able to give various commands. Commands 277would be things like: 278 279"Describe to me all ships you are tracking." This command would 280print a list of ships being tracked, the types, the number of 281possible locations for the ship, the time the ship was first seen, 282and any code used to represent that ship in tracking displays. 283Possibly, the likelihood that the ship has been destroyed would 284be displayed as well. 285 286"Display possible locations for a ship." This command would 287display the possible locations for a ship. Possible locations 288might be printed by highlighting the squares where the ship could 289be. 290 291"Stop tracking a ship." This command would delete information about 292a ship that the user assumed she had destroyed. Note that the computer 293will sometimes be able to tell that a tracked ship has been destroyed. 294The user might also give this command if a ship was presumed to have 295gotten itself lost. The computer might also stop tracking a ship if 296the number of possible locations for the ship gets large. 297 298To support the above, the user should be able to place fighters 299and ships in "Search and Destroy" mode. Here the user would specify 300a tracked ship that was to be searched for. The fighters and ships of 301the user would move in such a way as to minimize the size of the 302perimeter list for the tracked ship. 303 3045) It has been suggested that all pieces at a location be moved 305at once instead of skipping around the screen in the order the 306pieces happen to be allocated. For example, the user is often 307asked what to do with each of the armies aboard a transport. If 308the user knows there are five armies aboard, she may start hitting 309the 's' key to put those armies to sleep. If the user isn't paying 310enough attention, she may discover that she has just put to sleep 311some piece on a few squares away. 312 3136) When moving a ship or army toward a destination, or when 314moving a ship toward port to be repaired, the user will often 315want to avoid land that might contain enemy pieces. This functionality 316is partially implemented in that ships prefer to be at sea if there 317is nothing to explore. Pieces moving towards a destination also 318prefer to move so that they are in the middle of all the shortest 319paths to the destination. 320 321Despite this, it might be desirable to implement a movement mode 322whereby ships went out of there way to avoid the enemy. 323 3247) It should be possible for the user to obtain information about 325pieces which are contained within another piece. For example, 326it would be nice to know the movement function of every ship 327contained in a city, or of every army on a transport. 328 3298) The big problem... The user needs to type one hell of a lot 330of commands to control the movement of her pieces. I've implemented 331a lot of stuff to alleviate this problem, but lots more can be 332done. If we assume that everything is implemented as a "movement 333function", the following movement functions would be interesting: 334 335"load army" -- an army moves toward the nearest loading transport 336or transport producing city. Note that this is the same algorithm 337as that used by the computer. 338 339(For armies, there are really only 340three functions that are needed: "attack" (which is implemented) 341where the army explores a continent and attackes the enemy or 342unowned cities; "load" where armies leave a continent; and "unload" 343where armies leave a boat for some other continent. Also note that 344when I play the game, most of the commands that I give are commands 345to move the army to a place where a transport will pick up the army, 346commands to have the army wait for the transport and load, commands 347to put the army to sleep while it is being transported, and command 348to wake up and unload the armies.) 349 350"load transport" -- the transport is marked as "loading", and the 351transport moves toward the nearest loading army. 352 353"unload army" -- I'm not sure what this does, nor what "unload 354transport" does. Basically, I want some pseudo-intelligent mechanism 355for telling the computer not to ask me questions about armies on 356a transport until that transport reaches "something interesting". 357"load army" and "load transport" would be much easier to implement. 358Unloading is where intelligence and strategy can be important. 359 360"patrol" -- This causes a piece to move so as to decrease the 361likelihood that an enemy piece can sneak by. One method of implementing 362this would be for the piece to move toward the square two away that 363had been least recently seen. It might be desirable to constrain 364a patrolling piece to a relatively small area of the board. 365 366Note that the "Grope" command (or "explore" mode) is no longer of 367much use for armies. Possibly "attack" mode would be useful for 368ships and fighters. 369 3709) One possibility for all of the above might be to allow the 371user to specify some algorithm that describes how pieces should 372move. I've thought along the lines of letting the user specify 373some sort of macro, and letting the user specify the arguments 374to one of the 'vmap_find_*obj' routines. This might require the 375ability for the user to place arbitrary labels on any square. 376 377 378Game Modifications 379------------------ 380 3811) Mobile repair platforms. Currently a damaged boat moves very 382slowly towards the nearest city. A floating platform that could move 383towards damaged boats might be useful. Also, this little baby would 384stay out of cities and so not be capturable. Hits would be 1; strength 385zero; and speed might be greater than 2. 386 3872) Setting transports to have a strength of zero might be interesting. 388 3893) Implementing the world as a torus instead of a rectangle might 390be better. This means having the map wrap at the edges instead of 391terminating at the edges. 392 3934) Increase the "logistics" aspects of the game. What about 394oil, iron, food, etc? Oil might be used to determine the range 395of a boat or ship. Armies might starve without food. Iron might 396be necessary for building a ship. 397 3985) One of my goals has been to define lots of highly specialized 399pieces so that each type of piece must be built and used in order 400to have an effective strategy. In the original game of empire, 401I eventually developed a strategy whereby the only pieces I would 402build were armies and transports. The computer basically couldn't 403beat me unless we both started on the same continent and it lucked out. 404The game also ended within one hundred turns. 405 406Now, eventually, I might decide that the current program also has 407the same faults (in which case I'll tweak the computer movement 408algorithms so that it plays differently). 409 410However, I have been making changes to increase the specialization 411of all the pieces. 412 413Obviously, armies must be built because they are the only pieces that 414can capture cities. 415 416Obviously, transports must be built (on worlds that have a reasonable 417amount of water) because that's the only way an army can be carried 418to another city. Since transports don't move all that fast, and 419since transports are fairly weak, they aren't good for much else 420(in theory). 421 422Beyond this... Patrol boats and fighters are very similar. Both 423are fast, both are quickly produced, both have low hits. 424I suspect that an effective strategy could be developed where one 425or the other of these pieces, but not necessarily both, were built. 426Patrol boats have an advantage in their unlimited range. This makes 427them useful for extremely long range exploration. Fighters have 428an advantage in their great speed. This makes them extremely useful 429for tracking and patrolling. Fighters also have a sufficient range 430that they can easily move across the board from one city to another 431without really needing carriers. Possibly, the range of fighters 432is too great. Possibly, the range of fighters should be 16. 433(For purposes of user friendliness, the range of fighters should be 434a multiple of the speed.) 435 436Now, carriers, destroyers, subs, and battleships are very similar. 437Carriers and battleships have the advantage that they can take a 438beating and then be reparied. Destroyers and subs have the advantage 439that lots of them can be produced which increases the amount of 440territory that can be seen at any time. 441 442Decreasing the range of fighters might increase the utility of 443carriers, but then the user would probably build more patrol boats 444instead. 445 446So, I guess I'm looking for more specialized pieces. Mobile 447repair platforms are one idea. Satellites are an attempt at 448a second idea, but this idea needs more refinement. Currently, 449the computer does just fine without building satellites (as near 450as I can tell). Maybe satellites would be more useful if they 451were faster or scanned a larger area. 452 453 454User Comments 455------------- 456> empire is getting very good about asking me about all the troups on a transport, 457> etc. before going on to another piece, but its still not perfect. 458> 459> the computer still seems to be spending too much effort fighting, and not enough 460> exploring. i think i've got it beat, although i'm not sure yet. i was burning 461> transport after transport (of the computers) while he tried to take an island 462> from me. he finally succeeded, but i must have killed 8 transports in the 463> process (he got two of mine). 464> 465> early in the game, he had a real superiority with patrol boats, that was giving 466> me fits. but now i think i've got him, and am making it very hard for him to 467> move around. also, he still hasn't finished taking islands he's colonized-- 468> hopefully i'll be able to take some away from him. he should have consolidated 469> them long ago, and being harassing me. 470> 471> The satellite is fun, although i wish it would head into enemy territory 472> instead of back into mine. 473 474The first paragraph is a request that all pieces of a type in 475one position be moved before moving pieces of that type at 476another position. This fix should be combined with the needed fix 477to move all pieces on the screen before redrawing the screen. 478 479The second paragraph suggests to me that the computer should 480move lots of patrol boats and other support craft into an area 481to clear it out before moving in transports. The transports are 482too vulnerable, and the computer isn't defending them very well. 483Maybe what I mean here is that the computer should have a concept 484of "escorts". When moving a transport, a destroyer, sub, or at 485least a patrol boat should try and remain near by. Then if our 486transport gets destroyed by an enemy, at least there is some chance 487that we can kill off the attacker. 488 489Other problems probably exist in this area as well. Early in the 490game, the computer will see an unowned city and drop some armies on 491it. A little later the computer will notice that there is a user 492city on the same continent. Now, all the computer's transports 493go floating around that user city and dump armies on it. The computer 494has used massive amounts of resources to take a continent instead 495of exploring and sweeping up more easily defended continents. 496 497On the other hand, the computer is very "contentious". It's kind of 498fun to have the computer fighting so hard to keep me from taking its 499cities. Also, if I don't use the current strategy, there is a danger 500that the computer will not fight hard enough to keep the user from 501invading and taking a computer-owned continent. 502 503Colonization... The computer takes new continents very slowly. 504I don't know why. The computer should be producing armies in 505the first city it takes, and the computer will produce armies 506in new cities as long as it sees an unowned city to attack. 507Potentially, there is a problem in that the computer might not 508see an unowned city, even though there is lots of unexplored territory, 509and thus probably an unowned city, on the continent. 510 511The bigger problem seems to be that the computer is producing too 512many armies and not enough other stuff. In the particular game that 513these comments derived from, the computer had a massive continent 514that was smothered in armies. Instead of producing so many armies, 515the computer should have produced more fighters and non-transport 516ships. Tweaking the "ration?" arrays in compmove.c should make things 517better. 518 519Note that the user's strategy was to seek and destroy transports. 520The user would ignore other ships for relatively long periods of 521time for a chance to destroy one of the computer's transports. This 522strategy was quite effective; the user tended to be able to keep 523many more transports on the board than the computer. 524 525> planes aren't that useful even as they are--sure they're good for zooming 526> in and destroying the odd troop transport, but they're not that helpful for 527> exploration. i still suspect the optimal strategy is armies, transports, 528> and patrol boats, with a few planes. Later in the game planes become 529> useful because they can be gotten to the scene so quickly. If you want 530> to reduce them, how about reducing them to 24? Also, when a plane is 531> about to fly past the point of no return (return to anything) how about 532> a question, a la "troops can't walk on water, Sir?". as long as i can 533> override the objection, its not a problem. 534 535> oh, i think it would suffice to be able to launch satellites in a particular 536> direction. 537 538The first paragraph is a response to my suggestion that a fighter's 539range should be reduced to 16 so as to make patrol boats and carriers 540more useful. 541 542Maybe we should crank up the hits on the various objects. This 543would make attacks a little more deterministic. For example: 544 545armies: 2 armies 10 546transports: 2 transports 10 547fighters: 2 fighters 10 548patrol boats: 2 patrol boats 10 549submarines: 4 submarines 20 550destoyers: 6 destroyers 30 551carriers: 10 carriers 80 552battleships: 12 battleships 100 553 554But then we would have to worry about repairing armies? Or maybe 555the effectiveness of an army simply goes down when it doesn't have 556full hit points? This would also greatly increase the repair time 557of an object. Or maybe objects would be repaired two or 10 hits 558per turn. 559 560Other bugs... 561------------- 562 563Possibly displayed messages should be of two types: Important messages 564and non-important messages. After an important message, the computer 565would delay for the full amount of delay time. After an unimportant 566message, it might not do anything. 567 568 5691) The "m" and "n" commands should work in movement mode. 570They should also work when setting the function of a piece 571for a city. 572 5732) Should there be a way to tell the program you are done 574attempting to move a fighter, and don't ask me about moves 575seven more times? 576 5773) The program should use environment variables or command line 578arguments to supply the filenames for "empsave.dat" and "empmovie.dat". 579A command line argument would also be useful for telling the 580program how often the game should be saved. Actually, all 581command line arguments should have associated environment variables 582that can be used to set defaults. 583 584ESR: I've added a save-interval option, and another to set the 585savefile name. 586 5874) When the user types "q" to quit, the program should exit 588immediately if the game has been saved. If the game hasn't been 589saved, the user should be told, and asked if she really wants to 590quit. 591 5925) "Andrew Morrow" <amorrow@nouveausystems.com> reported this in 593August 2002: 594 595I am playing the version of vms-empire that you claim in your READ-ME 596to maintain. I noticed a bug vms-empire that I think you should 597know. Sometimes the program exits in util.c/check_cargo() at the line 598 599 ASSERT (q->owner == p->owner); 600 601At least one case where this can happen is when two opposing 602transports meet at sea. Somehow, an army can transfer to an enemy 603transport. I have not examined the exact line this happens on (maybe 604while attempting to attack the enemy transport or while executing its 605function to move a in particular direction?) but I have saved such a 606game, commented out this line, landed my transport (which has a 607computer army on board), and seen the computer army exit my 608transport. 609