OpenXcom Forum

OpenXcom => Offtopic => Topic started by: Nikita_Sadkov on January 03, 2019, 12:37:07 am

Title: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on January 03, 2019, 12:37:07 am
Hi, folks! I'm working on an XCOM inspired fantasy game. It is not a carbon copy, and the most striking difference is that I don't use RNG, leading to numerous different design decisions. For example, instead of chance to hit, to penetrate high defense armor, attacker has to spend action points. This allows for example using some at first glance useless unit, with a lot of action points, like say bird, to distract defender, while slow heavy hitter does the damage. The next difference is the shift towards spellcasting and terraforming map. For example, if player has imp worker, it can dig underground passage into a prison under castle, free inmates there and then attack the castle from underneath. The other way would be flying over moat (with flight spell or flying creatures), teleport there, pass through walls with wraiths (which also see through walls), create elevation to reach castle wall. Obviously, player can just storm the heavy guarded front gate.

The game engine also supports portals and large doors (you cant have a proper castle with puny little door). And AI uses them too.

Still the game borrows a lot of elements from Gollop's games, especially Lords of Chaos and XCOM. I.e. there is chryssalid style monsters and a raise dead spell producing undead units, which are very resistant to non-enhanced attacks. The game has a world map, invasion threat and randomly generated maps (cities, dungeons, etc...), but I also plan adding ability to play as bad guys instead.

Do you have any suggestions or wishes for such a game? For example, what do you think should happen if two units teleport into the same place or if unit tries to teleport into the fog of war ends up teleporting into a wall? For now, just strongest unit survives (i.e. the wall).

(https://i.imgur.com/Z5QBTue.png)
(https://i.imgur.com/af8IRwV.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: luke83 on January 03, 2019, 12:52:55 am
Very nice mate, i would like to test your game then i could you my 2 cents worth :), please PM me if you want a game tester.

Title: Re: XCOM Inspired Fantasy Game
Post by: Valken on January 03, 2019, 09:00:14 am
Beautiful pixel artwork! Would love to see a demo video once you have a working alpha build.
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on January 03, 2019, 01:15:09 pm
In deed it looks promising. Overall right now I only see couple of things that could be improved in graphics.
First of all this selection box should be have some graphics not some green lines (or it is only debug thing?).
Second is to show not visible tiles as black, right now edge of visibility look too "sharp" (tiles look like they hangs in space because you do not see other around).
Some thing like that is done by OXC. Probably best version would be if tile is show as black only if it is adjacent to visible tile. With this edges will look more pleasing and you will see this star background too

btw all star "spikes" should have same orientation: https://en.wikipedia.org/wiki/Diffraction_spike
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on January 03, 2019, 04:55:50 pm
First of all this selection box should be have some graphics not some green lines (or it is only debug thing?).
The cursor is a paceholder which will be eventually replaced with proper graphics.

Second is to show not visible tiles as black, right now edge of visibility look too "sharp" (tiles look like they hangs in space because you do not see other around).
Some thing like that is done by OXC. Probably best version would be if tile is show as black only if it is adjacent to visible tile. With this edges will look more pleasing and you will see this star background too
Yeah. Fog of war needs future improvements. But for now it is of lower priority, than implementing features. I'm curious how Magic & Mayhem and XCOM games implement FOW. I did it though bruteforce raycasting. But I doubt original XCOM used such resource intensive routine.

Anyway, the game has Facebook page. I will post future updates there:
https://www.facebook.com/groups/298041333699422/
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on January 03, 2019, 06:28:34 pm
Yeah. Fog of war needs future improvements. But for now it is of lower priority, than implementing features. I'm curious how Magic & Mayhem and XCOM games implement FOW. I did it though bruteforce raycasting. But I doubt original XCOM used such resource intensive routine.
This depends on number of "rays" you use and more importantly what limitation you can impose on this.
First of all this will be only calculated when unit move to next tile, this mean this will happens only once per second, in this time you could render normal graphic using raycasting.

Some time ago I added new light engine to OXCE that propagate more realistically (walls block it). Each source of light was separately calculated.
This was a lot more computation intensive that simple FOV calculation. Example of hardest case was opening doors when on one side of it rage fire storm.
Then I would need update around 20 source of light for some large area. Naive implementation give 1s lag each time you open/close door.
After adding lot of limits and optimizations now this is not visible (at least on my hardware :D).

https://github.com/Yankes/OpenXcom/blob/OpenXcomExtended/src/Battlescape/TileEngine.cpp#L399
https://github.com/Yankes/OpenXcom/blob/OpenXcomExtended/src/Battlescape/TileEngine.cpp#L503
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on January 03, 2019, 08:23:58 pm
It all looks very pretty and intriguing, but I assume you want honest feedback, so...

The "I don't use RNG" is a complete deal breaker to me. It's fine in a card game, but a combat strategy? Sorry, but no.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on January 04, 2019, 01:07:19 pm
Naive implementation give 1s lag each time you open/close door.
Yeah. That will get even more involved if you remove map height restriction. And suddenly you need to use something like octress to traverse the map. For example, I use use height=32, and that already forces me to use a lot of hacks, to avoid traversing every tile for FOW and pathfinding. Gollop was genius to implement that for Amiga! (an 80ies computer)

The "I don't use RNG" is a complete deal breaker to me. It's fine in a card game, but a combat strategy? Sorry, but no.

1. Random decisions are still allowed for AI. If AI has two similarly powerful spells, you will never know which one AI will use (unless you manage to lock AI's ability to cast that spell). Or say what route AI units will take to attack player.
2. Maps are randomly generated, with items also placed randomly.
3. Player creature and spell selection is also slightly randomized. There could be no elven mercenaries available at that time, because they are at war with dwarves. Or shortage of ingredients for that flight spell.

So there RNG is still here, just the non annoying kind. So if you want to polymorph that orc into a chicken, you will always get a chicen and not a dragon. So yeah, it is more of a puzzle game.

And the game is designed with multiplayer in mind, so RNG is a no-no for that. Unless you want players to insult each other about being lucky n00bs.

Although I still plan to add additional RNG-mode for players wanting that kind of experience of having to miss 50% of time. But that is of lower priority, because there already a lot of games with such RNG.
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on January 04, 2019, 01:50:54 pm
Thanks, I understand your decision.
It's just not a game for me... I don't care for e-sport mechanics. :P
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on January 25, 2019, 06:28:34 pm
Thanks, I understand your decision.
It's just not a game for me... I don't care for e-sport mechanics. :P
Yup. It is hard to make a game that will cater to everyone, so for now I'm trying to make something unique.

I also plan adding different campaign modes, beside scenarios and XCOM style: one roguelike, and the other similar to what you see in Cortex Command. In future I hope making it into a very modable open source engine, which could be used to implement any similar game, from games like Final Fantasy Tactics like to Dwarf Fortress and Minecraft type games.
Title: Re: XCOM Inspired Fantasy Game
Post by: FeruEnzeru[RETIRED/I QUIT] on January 25, 2019, 11:34:09 pm
@Nikita_Sadkov
In future I hope making it into a very modable open source engine, which could be used to implement any similar game, from games like Final Fantasy Tactics like to Dwarf Fortress and Minecraft type games.
Aw that's a good one! :)
Man, i wish XCOM:EU2012/EW (not Long War 1) was moddable til 2020s or 2030s instead of 2019/this year. :-\
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on January 27, 2019, 01:44:42 pm
Aw that's a good one! :)
Man, i wish XCOM:EU2012/EW (not Long War 1) was moddable til 2020s or 2030s instead of 2019/this year. :-\
I checked this XCOM reboot when it came, and found that the reboot is completely different game from original XCOM. It seems devs looked over screenshots from original XCOM and made unrelated game with the same name. Nice graphics, but everything else is static and scripted so tightly, you may as well watch a TV show instead. It is like visiting paleontology museum vs traveling with time machine to see real dinosaurs. Even worse story happened with System Shock reboot, where devs showed nice demo, made selfies with Warren Spector, collected money and ran away with them.
Title: Re: XCOM Inspired Fantasy Game
Post by: Stoddard on January 27, 2019, 03:51:43 pm
I checked this XCOM reboot when it came, and found that the reboot is completely different game from original XCOM. It seems devs looked over screenshots from original XCOM and made unrelated game with the same name.

There's project lead's interview floating on the net where he talks about making an true sequel prototype, presenting it and then Sid Meier showing him the light. Pathetic, really. But explains the mess.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 06, 2019, 03:10:01 pm
Made a playable preview release:
https://nikitasadkov.itch.io/spell-of-mastery-demo

Suggestions are welcome.

(https://i.imgur.com/PvGTCZY.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Stoddard on February 06, 2019, 05:57:38 pm
Made a playable preview release:
https://nikitasadkov.itch.io/spell-of-mastery-demo

Suggestions are welcome.


Cool! But it looks like you put lib directory instead of src or a link to github into the .zip

Edit: ah, now I get it. It's your own runtime and your own lisp. Very cool.
Title: Re: XCOM Inspired Fantasy Game
Post by: Meridian on February 06, 2019, 06:44:02 pm
Very nice colors and shades.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 06, 2019, 07:12:05 pm
Cool! But it looks like you put lib directory instead of src or a link to github into the .zip

Edit: ah, now I get it. It's your own runtime and your own lisp. Very cool.
Yeah I'm a big fan of Lisp, so I decided to write game in Lisp. Spell of Mastery is actually my second game. The first one was Warcraft 2 engine implementation in Common Lisp (SBCL). It was fairly complete with working AI and all spells implemented: https://www.youtube.com/watch?v=-k8jkeFfnl0
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 12, 2019, 02:02:09 am
Implemented fire, lightning and explosions burning grass and flammable objects. Also added a bugfixes to the demo at https://nikitasadkov.itch.io/spell-of-mastery-demo

Remaining major features:
1. Collapsing structures. This one require introducing material strengths. Metals can have large overhangs than soil.
2. Water/lava dynamics. Moving water is actually an important tactical feature. Say flooding a cave full of enemies. Or in multiplayer maps player can create bottleneck by flooding trenches. Fantasy setting makes it easy to introduce such feature, because there could be say a flood spell.
3. Passable objects blocking vision, like smoke screen or tall bushes, which could be especially useful to burn down.

(https://i.imgur.com/JW3VU0H.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 14, 2019, 02:51:13 am
Ok. Done implementing fog/tall grass blocking vision. Also fixed a ton of bugs. As always, comments and suggestions are welcome.

(https://i.imgur.com/nL6DjS1.png)

The Fog of War regeneration mechanics is actually allows some choices with various drawbacks. For example, FOW can be regenerated at the end of players turn, at start of player's turn, both at the start and at the end, or when any unit finishes movement. Deciding how to implement FOG of war, I made a pros/cons table (such tables appear to be a common game design instrument).

End of Turn:
- Pros:
  - Player doesn't see enemy movement in territories he left.
  - Player can still see enemies which killed his units or casted Mist.
  - Player can see all terrain he uncovered during this turn. Makes it easier for player to remember stuff. Especially if player loads the game after few days.
  - AI handles it easily, noticing positions of your units.
  - Intuitive.
- Cons:
  - Effects like Mist wont blocking vision won't be immediately noticeable.

Start of Turn:
- Pros:
  - Effects like mist blocking vision will be immediately noticeable.
- Cons:
  - Player can see enemy movement in territories he left.
  - Player can still see all enemy movement in mist until the start of his turn. That will be just an annoyance.
  - Really hard to make AI handle it.
  - Non-intuitive.

Both Start and End of Turn:
- Pros:
  - Some combined pros of both approaches.
- Cons
  - Really hard to make AI handle it.
  - Non-intuitive.

Each time unit finished its movement:
- Pros:
  - Very intuitive.
  - Spells like Mist immediately take effect.
- Cons:
  - Less tactical depth: player cannot move a scout close to uncover enemy units, then move that scout away and nuke the enemy with some area of effect spell, that would otherwise harm the scout.
  - Computationally intensive on large maps.
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on February 14, 2019, 09:28:03 pm
Some thoughts about mist and fire. Overall I think its look bit out of place and do not fit good rest of graphic. It look bit too much diffused compared to rest of sprites.
Overall graphic is nice looking pixel art and this effect look like from some 3D game.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 15, 2019, 07:55:13 pm
Some thoughts about mist and fire. Overall I think its look bit out of place and do not fit good rest of graphic. It look bit too much diffused compared to rest of sprites.
Overall graphic is nice looking pixel art and this effect look like from some 3D game.
There is a number of reasons I decided to use non-pixelart effects.
1. Alpha channel allows to easily show objects inside mist and fire. And blends nicely with any object, as opposed to say dithering. In XCOM artists had to keep flames really small and close to the ground to avoid obscuring units. You just don't get that massive firestorm effect burning trees. Same with mist, which should be the height of a unit to actually block sight, otherwise it will look silly.
2. It is a common practice to use alpha-channel true-color effects in modern pixelart turn-based games, and even in some older, like Age of Wonders (it combines index painted pixelart with pre-rendered graphics), Master of Magic, Magic & Mayhem and Mage Knight Destiny Soldier for GBA.
3. Full color gradients and transparency make special effects stand out.
4. You just cant nicely model mist and fire using pixels. Especially with large sprites. It will have a lot of ugly dithering, and nasty gradient jumps. I also found it much harder to produce good looking pixelart effects.
5. There is a good amount of ready to use true-color stock art effect templates, both free and commercial. Just load them into particle editor and create what you need. In fact, I had to convert a few pixel art effects I took from OpenGameArt into continuous color, because, while the effects were okay, they were looking just wrong with that dithering.
6. I still use pixelart for a few effects, like the magical goblet for bless spell.


Also, there is an indie game called, Waves of Fate, they do use pure pixel art effects in it (down to scary dithering in place of transparency), but it looks okay due to generally non-realistic art style: https://store.steampowered.com/app/467270/Weaves_of_Fate/

Then again, many older pixelart games, like Final Fantasy Tactics, combine everything that works. Although I always thought that FFT's 3d landscape is the ugliest part of the game, after the pre-rendered intro cutscene, which was outsourced to that infamous Russian studio, which made Zelda Phillips CDI games. Still FFT's 3d magic effects were really beautiful, and impossible to achieve with pixelart.
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on February 16, 2019, 01:40:01 am
You did not get exactly my point. I fine with transparency and special effects on graphic, some thing I did:

https://openxcom.org/forum/index.php/topic,1532.30.html
https://openxcom.org/forum/index.php/topic,322.msg4504.html#msg4504
https://openxcom.org/forum/index.php/topic,2059.0.html

I once made default fire semi-transparent in some old branch of OpenXcom.

My point was that graphic used for this effect was too much blurred compare to rest of graphic. Transparency can have impact on this but I do not think this main reason.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 16, 2019, 05:27:17 pm
My point was that graphic used for this effect was too much blurred compare to rest of graphic. Transparency can have impact on this but I do not think this main reason.
Well, it is a fog, it is supposed to be blurry and annoying to players. There are a few spells, like tornado to get rid of it.

Also, implemented rain effect, which would reduce sight, extinguish fires and prevent fire spells from being cast at outside locations. I'm unsure how much and when rain should go. Maybe the rain could be that one place where RNG will be allowed? I really want to avoid RNG and make game as fair as chess, but making it rain every 31st turn would look silly. Obviously rain should be controlled by biome, so there will be no rain in the desert, but a lot of rain in rainforest. Should rain spawn mist? How to spawn mist in deterministic way, without RNG? Then again, what do I know about raining? Or maybe making rain into a spell, casting which would change weather?
(https://i.imgur.com/NyvIq6T.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 18, 2019, 03:30:31 am
Dynamic water - done. In future I will also add lava, which would set nearby objects on fire and cool into stone under rain or in contact with water.

Still these liquid interactions are rather tricky and allow for a lot of possible implementation, with various drawbacks and game design shortcomings.

(https://i.imgur.com/luhKzVH.gif)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 24, 2019, 01:45:00 am
Ooookay. One huge update. Dunno if you people can implement the same in OpenXCOM  :P I'm sure in one thing, with XCOM style map cell format you will have to use different approach.

Version 0.9a changes:
- Smooth fog of war, due to multiple requests. For some reason people were really annoyed by contrast square fog tiles   :-\

Version 0.9 changes:
- Dynamic Water.
- Cataclysm spell to flood your enemies and open a passage through waters. Finally you can play as Moses!
- Tornado spell, which scatters units and removes mist.
- Proper time system, instead of abstract turns. Now every turn models real life hour.
- Night time: every 8 turns out of 24 turns day, from 22:00 to 6:00. Undeads have more defence at night, while units without darkvision have reduced sight.
- Rain, which extinguishes flames in outdoor areas and prevents the use of fire spells, like firestorm and fireball. Units inside rain get -1 to sight.
- Proper wood bridge tile, instead wooden floor.
- Fixed fog sight bug, when cell below or above give units cant be accessed inside fog.
- Fixed bug with invalid empty check, affecting several spells and leading to potential crashes when one creature teleports into another creature.
- Fixed crash hiding drowning unit.

(https://i.imgur.com/OSD4KZ8.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on February 24, 2019, 06:11:39 pm
(https://i.imgur.com/luhKzVH.gif)

Does it mean we can blow up parts of the map to drain water? :)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 25, 2019, 02:38:14 am
Does it mean we can blow up parts of the map to drain water? :)

Yup. It would also allow randomly generating puzzles, if water reservoirs are placed randomly. Although soil is really explosion resistant material, unless it is really heavy explosion leaving a crater, so currently I have limited terraforming only to the imp unit, which also digs passages, builds ladders and bridges. In XCOM game that would be a soldier with a shovel (I'm surprised OXC havent implemented trench digging yet). The flood/cataclysm spell was a little overpowered, so I had to reduce ranger and implement accretion time, so AI will have a few turns to move out of the way.

Here I imp below digged under the river, redirecting the flow and drowning in the process.
(https://i.imgur.com/RI9bx8O.gif)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on February 28, 2019, 09:49:53 pm
Done collapsing terrain, killing units caught inside and giving fall damage to the ones standing on top. Still needs some proper animations. IIRC, collapsing multi-floor buildings were major feature of XCOM Apocalypse. I haven't seen them in any other game.
(https://i.imgur.com/0JI93cF.gif)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on March 05, 2019, 10:47:36 pm
Original XCOM engine had somewhat intricate sprite format, requiring artist to carefully split sprites into into multiple cells. That was especially annoying with larger objects, like trees or tanks (dunno if Gollop had some cool algorithm to do that automatically). I just use free form sprites, leading to more complicated draworder algorithm, especially when most humanoids have a height of 2 cubes. I also limit movement direction to north,south,west,east, which requires me to draw sprites only in two directions. Still a lot of routine work.
(https://i.imgur.com/j63HGSl.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on March 05, 2019, 11:07:53 pm
Some interesting notes from original XCOM Apocalypse developer:
http://www.terrygreer.com/xcomapocalyse.html
Quote
The editor was an updated version of the one used for the earlier xcom games.

Every tile was designed to occupy a volume of space. Many tiles had multiple versions showing a succession of destroyed states.

In the description off each tile there was a series of properties such as ‘health value’ and ‘destroyed tile type’. when the health value was eroded away the tile would then be replaced by the ‘destroyed tile type’ (which in turn could have its own health and destroyed type). Chains like this could be as long or short as required. Tiles could of course also bed invulnerable.

This approach meant that potentially anything in the map could be blown apart and destroyed. This was made even more true in Apocalypse as tiles could also be flagged as supportive, and if a supportive tile was destroyed then those above it could also fall.

 

Tiles were complex data structures. Each one also had a reference to line of sight definition – this was a simple 4x4x4 grid – a sort 3d texture – where each cell was either solid or empty. There were a relatively small number of these solid line of sight definitions, but enough to approximate the 3D shape of any shape of tile created. This meant that the world was effectively broken into a 3d voxel grid where weapon fire could be accurately ray-traced. It was a ball ache to set up initially, as every tile had to have a line of sight definition assigned, but really made life easy later on as collision in game then became automatically generated from the map editor.

It was a genius approach, especially in the years before decent 3d raytracing – and one of the key identifying features of an xcom game. Players always loved being able to snipe enemy forces from right across the map through a couple of windows or blown open walls. It’s also a technique which I think useful to reinvent for use in conjunction with true 3D worlds and can think of lots of good mechanics you could use them for.

 

While some mission maps were hand crafted (especially apocalypse and the end missions of every game), many other mission maps in XCom games were made procedurally (especially in the earlier games).

 

The procedural rules would:

  1. Decide on the location type (e.g. farm, port, city etc)

  2. Then, using a look-up table specific to the location type selected a look up table would let a number of small hand crafted sections be chosen at random (though rules would restrict how often each piece could be chosen).

  3. Mix together these sections (with simple rules that specified which sections could be adjacent to which other sections).

The result was a vast number of possible layouts – for all intents and purposes near infinite, and unique to each user.

The procedural nature of these maps made the games feel more personal to each user.

The recent remake eschewed this approach and instead went for a large number of hand crafted maps instead, although with random starting points (which was a shame).

Sadly I don't have screenshots of the tools we used for these isometric games

Were these tools ever made public? Or maybe their code was left in the game's executable?
Title: Re: XCOM Inspired Fantasy Game
Post by: Stoddard on March 06, 2019, 12:52:40 am
many thanks for the link.

it only emphasizes why great games are not ever done by big or even medium-sized studios.

editor: no, while i'm sure it's still out there somewhere, it's hopelessly outdated anyway. we have MapView

the rest is documented in ufopaedia.org and the source code.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on March 06, 2019, 11:54:04 am
it only emphasizes why great games are not ever done by big or even medium-sized studios.
Yeah. That Terry Green also designed other cool and innovative games, such as http://www.terrygreer.com/xenomorph.html (a System Shock style game long before System Shock). https://www.youtube.com/watch?v=QKVNnnqyuZY

It was an obvious inspiration for System Shock, down to soundtrack.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on March 09, 2019, 03:10:11 am
Implemented different biomes. Because you cant have lava without snow :P

Things to do:
- Cell temperature, melting ice/snow and setting objects on fire. Then things like lava and fire could just increase the temperature of creatures caught inside them.
- Air/oxygen. Closed rooms with creatures lose oxygen level, making non-undead creatures to die.
- Lava damaging flyers staying over it (should come with the cell temperature).

Well it is hard keep todo list from growing, because many features come naturally. You need lava damage and convection, you have to implement air and cell temperature. Lava should be really hot inside closed spaces.

(https://i.imgur.com/3kQ1DTn.png)
(https://i.imgur.com/safbafK.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on March 09, 2019, 01:06:31 pm
Dude, you are insane in the best way possible.

If only you considered dice rolls... ;)
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on March 09, 2019, 07:26:31 pm
This is too insane :D
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on March 14, 2019, 11:38:07 pm
Dude, you are insane in the best way possible.

If only you considered dice rolls... ;)
I do consider them as an option, something like hardcore mode.

Anyway, further work on gas diffusion would be introducing the scent propagation: each scent has a umber of components, and different units emit different proportion of these components. So if you have say a dog on a team, it may sniff the scent of the alien hidding behind the corner. Or you may use it for the usual diffusion based pathfinding, which would reduce the otherwise complex pathfind problem to just O(1). And the scent diffusion is an embarrassingly parallel problem, so in real-time setting one can easily run diffusion on several CPUs, or update diffusion it once in a few game cycles, when there isn't much going on.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 01, 2019, 07:23:01 pm
Implemented halved tiles. When designing an isometric engine, there are numerous decisions one has to make:
1. Will the engine allow truly 3d world without hacks? Like i.e. room over room.
2. Would the game world be cell-based, continuous or combine both approaches?
3. For cell based worlds, one has to pick unit-sized cell. Like i.e. 32x32x32 cube of 1x1x1 voxels.
4. What would be the cell format? Are walls going to be embedded into tile as well as floor or use separate tiles?

For example,
1. Magic & Mayhem has cell based world, but uses 32x32x16 cells. That approach is simple and robust, but requires splitting everything into such very small tiles or use some ad-hoc hacks for topologicaly sorting larger tiles, so they won't be ovedrawn with tiles behind
2. Original XCOM uses 16x16x16 cells and embed walls and floor into these cells, making it very involved to say trace a bullet path, while walls look really thin and units cramped into walls. Now cels can block vision from one side, while allowing to see from another.  Such approach also greatly impedes dynamic effects, like water flows. XCOM also allows fatter walls, further complicating engine. Yet it is very efficient, because it greatly cheapens topological sorting and extends map size, because walls are stored as part of cell and sorted with it.
3. Furcadia uses approach similar to XCOM, but walls can have any height, yet they still look very thin.
4. Ultima 8 and Faery Tale 2 use continuous world approach with cell sized tiles.
5. Final Fantasy Tactics allows only varying floor height. Many similar games are lazily implemented by making each tile type into a long pilar, which is just moved up or down to accommodate for height, instead of introducing proper tiling and draw order sorting.
6. Diablo have just floor and objects on top of that floor. The simplest type of isometric game to make.
7. Stronghold used some very complex approach, basically splitting every building into very small cubes, supposedly automatically. All these crenelations on towers properly obscured units. One of the more complex isometric game engines. Still unsure how the implemented pathfinding.

Anyway, picking base cell size doesn't really limit tile size, with some hacks one can implement finer 16x16x16 tiles in 32x32x32 engine.

(https://i.imgur.com/8QI0EVW.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 02, 2019, 05:51:52 pm
XCOM like Fantasy game which came out two years before XCOM, but I bet you never ever heard of it:
https://www.mobygames.com/game/four-crystals-of-trazere
>Armies of mutants are marauding through the land and it's up to the heroes to scour the cities, dungeons, and wilderness looking for clues to the source of the evil. The party moves from location to location on a strategic map avoiding (or ambushing) enemy patrols and armies while trying to find the clues and items they need in isometric dungeons and cities. The game also features an intricate magic system that lets players design and customize spells.

The game has very involved magic system, where player can adjust spell area of effect, time and range. I.e. instead of a single shot dispel cast, player can have a dispel field, removing enchantment from creatures entering it. Really neat concept although hard to balance and implement properly. I had an idea of refactoring spells into such system, after getting over with the basic game.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 08, 2019, 09:34:38 pm
Another feature - colored lights for various effects. It is probably possible to ray-trace sun's position and shade terrain behind walls.

(https://i.imgur.com/mGSv7DU.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 09, 2019, 02:55:54 pm
Some tricky hacks are required to implement even the basic lights in an isometric engine. But lights are a must in a game heavily focused on magic and throwing fireballs, which would look very bland as static sprites.

Although the basic formula is very simple:
Code: [Select]
lighten T E = T + T*E/Factorwhere T is the texture's light receptiveness, and E is the light's energy. Of course you need to apply that formula to each of the RGB components, unless you have the stylish black & white soviet TV. I heard they still use B&W TVs in Russia :D

Alas I never got why applying light is multiplication, not addition. Guess that is some complicated physics shit with typical square law.

That guy from Stencil forum actually raytraced lights: http://community.stencyl.com/index.php/topic,41034.450.html

surprisingly his code is efficient enough to run even in browser, although slowly. At that level you can just use completely raycast engine. Then again, even my hacky code uses some degenerate form of raycasting. There just no going around traversing space, when you need to draw lights.

(https://i.imgur.com/vXkGlAE.gif)
(https://i.imgur.com/zfC3kEM.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Anon011 on April 09, 2019, 05:45:56 pm
Very nice game Nikita, I like it so far.
Will you make a Russian localization for it one day?
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 10, 2019, 12:27:54 am
Very nice game Nikita, I like it so far.
Will you make a Russian localization for it one day?
The programming language I use doesn't support unicode.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 10, 2019, 11:48:34 pm
Another tricky design decision: how to implement floating islands. The most robust way appears to be implementing special floating property for tiles. That way it could also be associated with some control structure, allowing it to move in 6 directions, maybe even landing and crushing units below. It would be near impossible to implement even a remotely challenging dueling AI in this setting (given that we still struggle to implement competitive AI for Starcraft), therefore such maps should be kept to XCOM style exploration, puzzles or multiplayer. Although I've plans implementing dueling AI, like in Magic & Mayhem, but on simpler arena maps, and giving AI some bonus, like several lives and more spells.

For now I've redrawn a public domain fir tree: https://opengameart.org/content/pine-tree-16x16

I dislike drawing, but not getting away from it, when there are no suitable free assets.

(https://i.imgur.com/cayKbVi.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 12, 2019, 12:06:59 am
Ok. Resized the tree to match the game proportions, and drawn another fir tree. These trees are a bit out of angle, and it can be fixed by scaling it by Y and adding a few backside slopes to branches, but that wont really make it look better - pure isometry is little bit too boring.

Also, in case of XCOM and Magic & Mayhem engine trees, the lower branches would be occluding the stuff on the ground, like the corn. While graphically correct, that isn't really a good thing, because occluded thing can be say an important key, fallen out of a dead monster, and because occlusion requires properly shading the object below (bright corn under branches will look incorrect).

(https://i.imgur.com/NAQvJlC.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on April 12, 2019, 09:34:50 pm
I for long time think amount 2.5D graphic engine. This mean that each screen pixel have not only color but depth too. With something like this drawing order will be only secondary thing. You will check for each pixel you draw if you it behind or on front of background pixel.

With something like this you could add shadows too, special surface that have two depths, if background pixel have depth that is in this range we change shade of this pixel.

Overall each blit function will have not only `x` and `y` but `z` coordinate too.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 15, 2019, 01:52:04 am
I for long time think amount 2.5D graphic engine. This mean that each screen pixel have not only color but depth too. With something like this drawing order will be only secondary thing. You will check for each pixel you draw if you it behind or on front of background pixel.
That is called z-buffering. It is slower than draw-order sorting and doesn't solve the problem of higher layer popping through the layer below, or floor in front of a sprite cutting legs off large characters (that is why XCOM tanks are split into several cubes). Here is an example from Daimonin of what happens with naive approach (notice the cut off dragon legs and the poor botched wurm)
(https://i.imgur.com/xoshUcD.png)

To solve the problem you need actual 3d transformations,  and mapping each sprite as texture to a polygon. I actually tried doing it in software and it is orders of magnitude slower than topological sort. Although Ultima Online did it somehow in 90ies. I.e. it needs OpenGL, which requires 32bit textures in precise 512x512 pages, forcing to pack all graphics into such pages, which requires writing very tricky packing algorithms. In addition OpenGL doesn't support paletted textures, so no way to recolor units or do color cycling, so you need write a lot of tricky shaders to support that. And you will still need to sort transparent surfaces, which is especially nasty, when most of your sprites have some transparency. It is also harder to control 3d polygons. For example, same cell may have a pebbles sprite, a unit standing on top of said pebbles, a weapon that unit is holding and some effect, like explosion or fire over that unit. These elements should be drawn in that precise order, it would be silly if weapon gets drawn before the unit.

So yeah, OpenGL and any 3d brings in more problems than it solves. And of course say good bye to portability, because each graphics card does something differently.
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on April 15, 2019, 09:24:24 pm
You missed one important aspect, EVERY pixel have depth, this mean destination and source too. If unit clip it should look like it dive into water.
And performance will not be very bad, OXC already do half of work that I image will be needed. Overall my idea how it will work is based on my work on OXC.
I already use some custom surfaces to make some special effects, like globe illumination using normal vectors. All done in software.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 16, 2019, 04:24:51 pm
You missed one important aspect, EVERY pixel have depth, this mean destination and source too. If unit clip it should look like it dive into water.
And performance will not be very bad, OXC already do half of work that I image will be needed. Overall my idea how it will work is based on my work on OXC.
I already use some custom surfaces to make some special effects, like globe illumination using normal vectors. All done in software.
Triangle rasterizing code is much slower than a direct blit, even if you optimize it with SSE. For each sprite you will have to project 4 vertices, draw 2 triangles, interpolating Z and UV across them. Here is the bare minimum to implement OpenGL-like triangle drawing in software:

Code: [Select]
static void draw_span(lerp *l, int y, int x, int end_x) {
typedef unsigned short fixcol;
#define fix(x) ((fixcol)(signed short)((x)*0xffff))
#define unfix(x) ((float)(x)/(0xffff))

int tt[640];
memset(tt, 0, 4*640);

// color layout: AAAA|RRRR|GGGG|BBBB

Uint16 mm0[4];
mm0[3] = fix(A(l));
mm0[2] = fix(R(l));
mm0[1] = fix(G(l));
mm0[0] = fix(B(l));

Uint16 mm1[4];
mm1[3] = fix(AD(l));
mm1[2] = fix(RD(l));
mm1[1] = fix(GD(l));
mm1[0] = fix(BD(l));

Uint16 mm2[4];
mm2[3] = fix(0.0); // ambient color shouldn't affect alpha
mm2[2] = fix(ambient_r);
mm2[1] = fix(ambient_g);
mm2[0] = fix(ambient_b);

// uv layout: 0000|0000|VVVV|UUUU
Uint16 mm6[4], uv_delta[4], uv_wh[4], uv_bp[4];

mm6[0] = fix(U(l));
mm6[1] = fix(V(l));
mm6[2] = 0;
mm6[3] = 0;

uv_delta[0] = fix(UD(l));
uv_delta[1] = fix(VD(l));
uv_delta[2] = 0;
uv_delta[3] = 0;

uv_wh[0] = texture->w-1;
uv_wh[1] = texture->h-1;
uv_wh[2] = 0;
uv_wh[3] = 0;

uv_bp[0] = texture->format->BytesPerPixel;
uv_bp[1] = texture->pitch;
uv_bp[2] = 0;
uv_bp[3] = 0;

fixcol one[4] = {0xffff, 0xffff, 0xffff, 0xffff};
float z = Z(l);
float zd = ZD(l);

Uint8 *dst = (Uint8*)screen->pixels + y*screen->pitch +
x*screen->format->BytesPerPixel;

// now we have following arrangements:
// EAX is temporary
// EBX points to zbuffer
// ECX is used for debugging
// EDX holds final location in screen buffer
// ESI points to texture
// EDI points to screen buffer
// MM0 holds light color
// MM1 holds delta for light color
// MM2 holds ambient
// MM3 holds resulting color between stages
// MM4 is temporary
// MM5 is temporary
// MM6 holds uv
// MM7 holds 0
// XMM6 holds Z
// XMM7 holds Z Delta
// others are unsed
// MMX code assumes that botch: screen and textrue are in BGRA format
asm (
"movq %0,%%mm0\n\t"
"movq %1,%%mm1\n\t"
"movq %2,%%mm2\n\t"
"movq %3,%%mm6\n\t"
"pxor %%mm7,%%mm7\n\t" // mm7 = 0

"movss %8,%%xmm6\n\t" // z
"movss %9,%%xmm7\n\t" // zd

"jmp loop_start\n\t"

"loop_body:\n\t"

// Z-BUFFER TEST
"test $1, %%ecx\n\t"
"jz skip_ztest\n\t"
"movss (%%ebx), %%xmm5\n\t"
"cmpss $2, %%xmm6, %%xmm5\n\t" // xmm5 <= xmm6
"movd %%xmm5, %%eax\n\t"
"test %%eax, %%eax\n\t"
"jz loop_advance\n\t"
"movss %%xmm6, (%%ebx)\n\t" // save new z-value of this pixel
"skip_ztest:\n\t"

// TEXTURE MAPPING (mm3 holds result)
"movq %%mm6,%%mm3\n\t" // mm3 = uv
"pmulhuw %5,%%mm3\n\t" // mm3 = u*w, v*h
"pand %5,%%mm3\n\t" // mm3 = (u*w)%w,(u*h)%h : wrap
"pmaddwd %7,%%mm3\n\t" // mm3 = linesz*vh+colorsz*uw
"movd %%mm3,%%eax\n\t"
"movd (%%eax,%%esi),%%mm3\n\t" // mm3 = packed_texture
"punpcklbw %%mm7,%%mm3\n\t" // mm3 = texture

// LIGHTS (mm3 holds result)
"test $2, %%ecx\n\t"
//"jz skip_lights\n\t"
"movq %%mm0,%%mm4\n\t" // mm4 = light
"pmulhuw %%mm3,%%mm4\n\t" // mm4 = light*texture
"pmulhuw %%mm2,%%mm3\n\t" // mm3 = ambient*texture
"paddusb %%mm4,%%mm3\n\t" // mm3 = (light + ambient)*texture
"skip_lights:\n\t"

// BLENDING (mm3 holds result)
"test $4, %%ecx\n\t"
"jz skip_blending\n\t"
"pshufw $0xff,%%mm3,%%mm4\n\t" // mm4 = src_alpha
"psllw $8,%%mm4\n\t" // convert mm4 to fixed point
"pmulhuw %%mm4,%%mm3\n\t" // mm3 = src*src_alpha
"movq %6,%%mm5\n\t" // mm5 = 1
"psubw %%mm4,%%mm5\n\t" // mm5 = 1-src_alpha
"movd (%%edi),%%mm4\n\t" // mm4 = dst_packed
"punpcklbw %%mm7,%%mm4\n\t" // mm4 = dst
"pmulhuw %%mm5,%%mm4\n\t" // mm4 = dst*(1-src_alpha)
"paddw %%mm4,%%mm3\n\t" // mm3 = src*src_alpha + dst*(1-src_alpha)
"skip_blending:\n\t"

// ENDING
"packuswb %%mm7,%%mm3\n\t" // pack pixel in mm3...
"movd %%mm3,(%%edi)\n\t" // and puti it to final resting place

// ADVANCE
"loop_advance:\n\t"
"paddw %%mm1,%%mm0\n\t" // advance light
"paddw %4,%%mm6\n\t" // advance uv
"addss %%xmm7,%%xmm6\n\t" // advance z
"add $4,%%edi\n\t" // advance x
"add $4,%%ebx\n\t"

// LOOP CONTROL
"loop_start:\n\t"
"cmp %%edx,%%edi\n\t"
"jl loop_body\n\t" // jmp if edi < edx

"emms\n\t" // reset FPU after MMX
:
:
"m" (*mm0), // 0
"m" (*mm1), // 1
"m" (*mm2), // 2
"m" (*mm6), // 3
"m" (*uv_delta), // 4
"m" (*uv_wh), // 5
"m" (*one), // 6
"m" (*uv_bp), // 7
"m" (z), // 8
"m" (zd), // 9
"c" (flags), // ecx
"b" (zbuffer+y*screen->w+x), "d" (dst+(end_x-x)*4),  "D" (dst), "S" (texture->pixels)
);
}
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on April 17, 2019, 04:16:39 am
I want 2.5D engine, not 3D engine :>
I not even try implement drawing triangles. Simply biting 2D sprites with depth (that can be implemented as two normal surfaces but one is not treated as color but as depth).

https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L987
https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L175
This is shading I spoke before, each pixel have predefined normal vector and based on this I calculate sun shading on globe.
And everything still 8bit.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 17, 2019, 05:05:04 pm
I want 2.5D engine, not 3D engine :>
I not even try implement drawing triangles. Simply biting 2D sprites with depth (that can be implemented as two normal surfaces but one is not treated as color but as depth).
Where will you get the depth surface? 3d software generates it together with sprite? I remember there was some zombie-shooter game demo, where artists hand-drawn such z-surface onto each pixelart sprite, so dynamic light would highlight these sprite properly from any angle. A ton of work, and I havent heard about them since then. Guess their project is dead. And as I said with just z-buffer you will still get wrong draw order like: https://www.youtube.com/watch?v=BJYH-UrQ2xs
That guy solved it with two zbuffers, one for draw order, another the usual depth buffer. I solved it with topologically linking objects in a tree of what occludes what, but did that locally and only for specific units. I'm not using zbuffer now (although I had it in the first version), instead just sorting by x,y,z towards frustum.


https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L987
https://github.com/Yankes/OpenXcom/blob/master/src/Geoscape/Globe.cpp#L175
This is shading I spoke before, each pixel have predefined normal vector and based on this I calculate sun shading on globe.
And everything still 8bit.
XCOM globe is an actual 3d object, so you get normal vectors for free with it.
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on April 17, 2019, 07:41:57 pm
Where will you get the depth surface? 3d software generates it together with sprite? I remember there was some zombie-shooter game demo, where artists hand-drawn such z-surface onto each pixelart sprite, so dynamic light would highlight these sprite properly from any angle. A ton of work, and I havent heard
about them since then. Guess their project is dead.

Yes, you need prove it as separate surface, this need be lot of simpler than doing main graphic on its own. Flat shades that represents different depths could be enough in 99% cases. Alternative could be done using approximation form main graphic (inner parts should have more thickness that edges).

And as I said with just z-buffer you will still get wrong draw order like: https://www.youtube.com/watch?v=BJYH-UrQ2xs
That guy solved it with two zbuffers, one for draw order, another the usual depth buffer. I solved it with topologically linking objects in a tree of what occludes what, but did that locally and only for specific units. I'm not using zbuffer now (although I had it in the first version), instead just sorting by x,y,z towards frustum.
I do not think he use z-buffer in same way as I thinking how it should be used. You could consider each pixel of graphic as voxel in space 3D space. How one voxel with less z can occlude voxel with bigger z? Trick is that flat tiles shroud have ramp in z values, and tile ramps in some cases should have flat z values (this depend on angle of ramp compare to screen). You could even blit together background as one surface and reuse it in each frame.

This is important difference. You can see in this YT video that this buffer get brighter when it going to left side, this is wrong, it should be brighter when going to bottom edge of the screen.

I dig up my very old z-buffer test. Example in images. Red circle is draw as last but it overwrite all green "boxes". Second image is normalized z-buffer.

XCOM globe is an actual 3d object, so you get normal vectors for free with it.
globe is not 3d object, its drawn using 2d polygons, all 3d math is done on our side. Normals are only avaialbe because we know that globe is sphere, with this I can precalculate them for each pixel of screen and zoom level.

https://github.com/Yankes/OpenXcom/blob/OpenXcomExtended/src/Geoscape/Globe.cpp#L914
https://github.com/Yankes/OpenXcom/blob/OpenXcomExtended/src/Geoscape/Globe.cpp#L1988
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 17, 2019, 11:09:20 pm
globe is not 3d object, its drawn using 2d polygons, all 3d math is done on our side. Normals are only avaialbe because we know that globe is sphere, with this I can precalculate them for each pixel of screen and zoom level.
Reminds me of Ecstatica, but they actually preserved all 3d geometry from the raytrace stage to properly occlude everything:
http://dingevoninteresse.de/wpblog/?cat=12

During the raytracing stage they also used really interesting texturing method by filling rocks with randomly placed sharp boxes, and organic objects with ellipsoids, instead of modelling then in a 3d editor. They had no 3ds Max or Maya back then, or large memory sizes to push that many polygons even for offline rendering. That gave the game its immediately recognizable clean art style.

(https://i.imgur.com/lKqWkUT.jpg)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 19, 2019, 03:28:02 pm
With a game world split into discrete cells, especially large ones, there is another tricky design moment: picking hexes or squares. Squares are a bit easier to implement, yet naturally allow movement into only 4 directions. That is - squares create space with non-Euclidean topology and use Manhattan distance as a metric. Of course, trying to remedy that, you can also allow diagonal movement, opening a can of worms on its own, because units now move diagonally faster than they do horizontally. Surprise!

You can try solving that by further replacing the discrete number of action points with say a floating point number, subtracting 1.41421356237 for each diagonal move, instead of 1, but sqrt(2) is an irrational number, so there will always be some bias, unacceptable for a competitive turn-based strategy. Even worse, if you have two walls, sharing a corner, then a unit could still stick through it, even if it looks impassable.

(https://i.imgur.com/fMbbnUy.png)

Diagonal movement is clearly bolted on, but moving in just 4 directions would be too inaccurate and limiting for an strategy game, and that is why people prefer hexes to squares.

Yet with picking hexes, we have to make another important design decision: hex lattice can be rotated differently on screen. For example, Heroes of Might & Magic uses grid with vertically shared edges, while Battle for Wesnoth uses horizontally shared edge.

The case of vertical sharing allows for wide-screen friendly viewport, when each player has its own side of field, and units move without zig-zaging. Battle for Wesnoth maps on the other hand tend to placing two opponents at the north and south, because movement east and west will go in zig-zag.

Heroes of Might & Magic style grid also cheapens graphics production. In Wesnoth they have to draw units both facing south and north, while HOMM unit's sprite can be simply mirrored. That is in addition to nicer looking diagonal walls on castle siege maps. That saves both artist's time and and video memory.

Another decision is how to lay out hexes in a map. Obvious decision is to lay them in a square grid. Yet it would be a very bad idea to organize hexes as a square. A round world would be orders of magnitude better, as it allows easily making well balanced symmetric maps for any number of players, instead of just 4 corners or 4 edges of square grid. Round maps are important, because in hexagonal world area of effect and just larger structures too have hexagonal form. That is in addition to simplifying programming (it is a tricky task to pack hexes into a box).

That what they call good design - not fighting mathematics, but go along with it.

TLDR: my biggest mistake was picking squares over hexes. I would recommended hexagonal lattice even for real-time strategies. Unfortunately Blizzard doesn't feel enough competition to fix their competitive games and make the next Stracraft into a perfect game.


(https://i.imgur.com/Czy4mR9.jpg)
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on April 19, 2019, 03:41:34 pm
I gotta say though, I hate hexes with a passion. The reason is simple: you can go in a straight horizontal line, but not vertical (or vice versa). This feels pretty shitty.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 19, 2019, 09:49:51 pm
I gotta say though, I hate hexes with a passion. The reason is simple: you can go in a straight horizontal line, but not vertical (or vice versa). This feels pretty shitty.
That can be remedied a bit by moving units vertically, when that is possible (i.e. there are no blocking units or triggers in the way), but only visually, behind the scenes units would still move on the lattice. In case of RTS, that will require more hacking obviously. Of course wargames, like Panzer General, move units directly in straight line right to their destination.
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on April 19, 2019, 09:58:20 pm
That can be remedied a bit by moving units vertically, when that is possible (i.e. there are no blocking units or triggers in the way), but only visually, behind the scenes units would still move on the lattice. In case of RTS, that will require more hacking obviously. Of course wargames, like Panzer General, move units directly in straight line right to their destination.

I'm fine with dirty tricks. ;)
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on April 20, 2019, 07:47:48 pm
One solution would be not use hex but triangles, if they are arranged in hex then you keep all hex good properties but you still can have orthogonal moment.
Trick is that 1TU allow you to move thought 2 triangles. I added small graphic that show this, All red dots are valid unit positions, black lines are allowed "half" moves. Effective this is multiple hex grids overleaped on each other.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 21, 2019, 03:08:18 am
One solution would be not use hex but triangles, if they are arranged in hex then you keep all hex good properties but you still can have orthogonal moment.
Trick is that 1TU allow you to move thought 2 triangles. I added small graphic that show this, All red dots are valid unit positions, black lines are allowed "half" moves. Effective this is multiple hex grids overleaped on each other.
Yeah. That could work. And you can still reuse the same hex tileset.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 21, 2019, 01:15:23 pm
Digging out procedural map generation. The following appears to be the state of art:
https://github.com/redblobgames/mapgen4
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 21, 2019, 05:20:08 pm
A reverse engineered explanation of the original Civilization map generation algorithm:
https://forums.civfanatics.com/threads/civ1-map-generation-explained.498630/

basically, Civ1 accumulated several random-walks, and then fixed the resulting map so unit wont be moving across what appears impassable body of water.

I've used similar code in my ancient Warcraft II map generator: https://github.com/saniv/wc2gen/blob/master/src/wc2gen.c

But instead of random walk patches, I've just put several seeds, and then applied cellular automation to the whole map, first for landmasses, then for hills, and then for forests. After that trying to place resources and player bases.

Mapgen4 also uses same tactics with placing emitters, but then builds voronoi polygonal surface, instead of running cell automata or random walk.

Alternatives: fractal generation, with midpoint displacement; overlaying some noise functions (like Minecraft does with perlin noise); and XCOM and Spelunky style of combining premade map pieces (Minecraft also embeds premade pieces inside noses-function generated map).

Instead of voronoi, one can probably uses other methods to interpolate inside point cloud, like quadtrees or metacircles: https://dribbble.com/shots/1776495-Metacircle-effect-source-file
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 23, 2019, 07:14:52 pm
Decided to use midpoint displacement. It is trivial to implement, and orders of magnitude easier to control, compared to say perlin noise, voronoi or random walk. Although one can surely tweak random walk to produce something similar to midpoint displacement. In the end, all these methods are closely related.

Also, naive perlin noise generator producing circular(!) rivers:
https://mccormick.cx/news/entries/blog-post-game-code-dabbling

But yeah, some people love crazy abstract stuff. Many fans very unhappy when Minecraft's map generation got tuned down to be less extravagant, killing stuff like overhanging terrain.

(https://i.imgur.com/zBiFeRj.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 24, 2019, 03:31:44 pm
Solved the concave polygon render with multi-pass raster scan, without any flood fill queue. Comes out nicely with a tail of islands on demand. Mirroring it would produce figures for a new Rorschach test :D

The shapes are still triangle based, but I can also fed in a rectangle or a hexagon or any polygon.

It is also useful to rotate these brushes, so had to invent the algorithm to rotate a point P around the origin O:

Code: [Select]
rotate A O P =
| Dir = P-O
| DX,DY = Dir
| CosA = A.cos
| SinA = A.sin
| NX = DX*CosA - DY*SinA
| NY = DY*CosA + DX*SinA
| [NX NY]+O

The hardest part is noticing that you don't need to compute the length of P-O, because division by it gets cancelled anyway.

(https://i.imgur.com/7c63s3n.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: ohartenstein23 on April 24, 2019, 06:47:52 pm
A while ago I was looking into map/globe generation for OpenXcom, was inspired by the world generator at https://donjon.bin.sh/world/ (https://donjon.bin.sh/world/). I liked the method of using randomized great circle slices of the globe since instead of needing a pre-defined grid of points for a height map, you can generate the polygons by storing the intersections of the great circle cuts. I ended up having to reduce them to triangles later to fit the way X-Com globe data works, and never really completed the generator, but I do have some WIP results posted here on the forums (https://openxcom.org/forum/index.php?topic=5955.0).

If I pick it up again, I'd probably need to add some functions after the initial polygon generation to randomize the coastlines a bit, since they tend to bear the hallmark of the great circle lines, making them look boring and obviously computer-generated.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 25, 2019, 09:26:09 pm
If I pick it up again, I'd probably need to add some functions after the initial polygon generation to randomize the coastlines a bit, since they tend to bear the hallmark of the great circle lines, making them look boring and obviously computer-generated.
I doubt there are any better algorithm than the midpoint displacement, which is very robust, corresponds to real life islands and can fill-in very precise shapes with arbitrary constraints.

People also use it to generate electricity or lightning like effects. And it also can serve as an input for sound generation, if you need some beefy synthetic sound  effects for your sci-fi setting video or game https://soundcloud.com/nikita_sadkov/explosion

I.e. the algorithm is a goldmine of cheap content, when you have no money to pay artists or sound designers.

(https://i.imgur.com/CCQm7JU.png)

Although I've found that the midpoint algorithm on a square grid has apparent bias, because it needs to sample from all 8 nearby cells, but the distance to four cells is 1, while distance to the four other cells is sqrt(2), meaning that N,S,W,E directions have less influence that they should, so the result isn't perfectly random and has predictable patterns, like say 45 degree lines are 1.4 times more likely than 90-degree ones. I.e. again we have that nasty square situation :D Googling has shown that people fix this sampling bug using some advanced math, beyond my grasp. But I'm sure it can be fixed by using hexagon grid instead, and then sampling down to squares. Still for my purposes these subtle errors ain't that noticeable and diagonal walls look more gamey.

Anyway, here is the current state of island generation. Several of these islands will be merged together to create game world.

(https://i.imgur.com/GGFK2vX.png)
(https://i.imgur.com/pMidLdS.png)
(https://i.imgur.com/6YBtfW0.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 28, 2019, 12:38:44 am
Slowly it comes to something usable in the game. Tilesets taken from Freeciv  :P
(https://i.imgur.com/VsxHCxH.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: luke83 on April 28, 2019, 04:54:22 am
wow, looking good.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on April 28, 2019, 03:54:05 pm
wow, looking good.
Unfortunatelly it is a bit tricky to generate rivers. One may suggest a simple gradient descent, but then rivers will end at a local minima. So it requires waterflow and erosion simulation to get out of local minima, without flooding like half of the island into a swamp. It is easier with the graph methods, where one can just send waterflow along the edges.

(https://i.imgur.com/DbhZyrQ.png)
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on April 28, 2019, 04:39:23 pm
Why not just flood half of the island into a swamp? I see nothing wrong with it. ;)
Title: Re: XCOM Inspired Fantasy Game
Post by: Yankes on April 30, 2019, 12:59:49 am
Why not just flood half of the island into a swamp? I see nothing wrong with it. ;)
Typical for Troll :>
Title: Re: XCOM Inspired Fantasy Game
Post by: Solarius Scorch on April 30, 2019, 09:45:36 am
Typical for Troll :>

An ogre! Ogre! :)
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on May 11, 2019, 01:37:31 am
Finished the initial version of island generator. For now it is good enough to test gameplay. Random generation is surprisingly methodical, it appears there is just one right way to do it, but countless wrong ones.
(https://i.imgur.com/j3rulgy.jpg)
Title: Re: XCOM Inspired Fantasy Game
Post by: luke83 on May 11, 2019, 02:02:45 am
Looking god mate, reminds me of Heroes of might and magic.
Title: Re: XCOM Inspired Fantasy Game
Post by: Nikita_Sadkov on May 11, 2019, 01:28:03 pm
Looking god mate, reminds me of Heroes of might and magic.
It doesn't really have much in common. HOMM3 obviously used voronoi diagrams to generate maps, judging by the geometrically perfect biome shapes. I'm not using them, because they don't appear to have any advantage over fractals and harder to control. Especially when it comes to placing roads and rivers. With fractals, you have mountains, rivers and forests forming naturally, which give birth to settlements, which are then connected with roads. With voronoi people typically placed rivers/roads along voronoi cell edges. It is also easier to fine-tune fractals by say replacing random with statistically correct data, so you could get islands having curvature similar to that of Ireland, or some Moon crater :D

Also, for now I've reduced the amplitude of road variation, as it was too noisy.

(https://i.imgur.com/W2e7nHf.jpg)
(https://i.imgur.com/q7w0Hve.png)