Author Topic: Battlescape progress and questions  (Read 2382 times)

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #15 on: October 08, 2016, 03:25:05 pm »
And another problem with vanilla's collapsible map logic


These yellow things (one marked by red circle) should not stay there. Their "supported by" type is "below" - meaning, they should not get support from above. They could get support from the sides, (marked by black circle), but those are marked as "flase" in "provides support" flag. This flag is unset for things that should NOT provide support - things like small features - robots, tables, floor rubble. It is also unset for those map parts. Below them is also nothing. Therefore, there is zero reason for them to stay there, yet they stay there and don't fall.

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #16 on: October 09, 2016, 06:03:39 pm »
Also, bugs in original maps become apparent now.

For example, battleship has floating "rubble" scenery located at the middle of western map edge at ~level 5.

Bomber has floating "stick" (it's a wall that looks like a pole) above it's northen lift (it's hard to see, it's located 1 tile northwest from lift's northwestern tile, on level 3).

What do we do with it? Let it fall? Make it magically float in the air?

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #17 on: October 10, 2016, 11:52:09 am »
Aaaaand.... Bad news is, we need a new tile rendering algorithm!

Implementing falling map parts unearthed something we cannot implement in our current algorithm, that draws objects in layers (first z0, then z1 etc.)


(There is a typo, 0,1,0 on the right should read 1,0,0)

As you can see, we have scenery (indicated with yellow arrow from the left) and two walls. Assume the coordinate of the tile scenery is falling into is 0,0,0 on x,y,z. In that case, wall to the right (bottom right arrow) is the left wall of tile 1,0,0 and wall to the top (top right arrow) is the right wall of tile 0,0,1

Now, falling scenery indicated with middle left arrow is either located in 0,0,0 or 0,0,1.
- In case it is located in 0,0,0, the wall at 0,0,1 will be drawn over it
- In case it is located in 0,0,1, the wall at 1,0,0 will be drawn under it.

We need to somehow change our rendering algorithm to handle this case properly
« Last Edit: October 13, 2016, 07:24:28 am by Istrebitel »

Offline JonnyH

  • Official Developer
  • Full Member
  • *
  • Posts: 152
    • View Profile
Re: Battlescape progress and questions
« Reply #18 on: October 12, 2016, 02:28:31 am »
There's also a number of 'bugs' in the cityscape with seemingly unsupported tiles, some grass in one of the walls, and a sewerage plant owned by 'X-Com' that I remember. I suspect the support issues weren't noticed as the original didn't check for tile support unless an adjacent tile was destroyed, so if they started 'magically hovering' they would remain there until something nearby happened to cause them to get re-checked.

As for the rendering order, we can pretty simply change x/y/z order when looping through the map, though your example appears like this isn't really enough.

what we could do is loop each 'z' level as the outermost loop, then draw all 'static' scenery on that Z level, then on top of that draw any 'falling' scenery, though the cost of looping through all tiles in the render is quite high on the profiler already, there's plenty we can do to make that faster, so don't worry about that for now.

Again with your example, I would assume that the walls in {1,0,0} and {0,1,0} would be correct in being drawn on top of the 'falling' scenery at {0,0,0}? As it'll be falling 'behind' the walls? Does the original draw it on top? Maybe 'falling' tiles are considered to be at the higher Z for longer than we do? (I believe we draw based on the 'middle' of the tileObject, maybe the original actually did the 'top' of the object?)

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #19 on: October 13, 2016, 07:35:24 am »
I am not sure I undestand your question, but I've noticed I made a mistake, it's not a 0,1,0 wall but 1,0,0 wall. It doesn't change much though. Screenshot is from vanilla, and this is how it should be drawn. 1,0,0, and 0,0,1 both must be drawn above falling scenery from 0,0,1 to 0,0,0. It's falling behind those walls.

Assuming falling scenery is drawn in 0,0,1, draw order is:
...
0,0,1
...
1,0,0 / 0,1,0
..


Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #20 on: October 13, 2016, 07:48:35 am »
And thing is, here's another case

There is no right wall in 1,0,0, it's actually a scenery at 1,-1,1, but imagine there actually is one. I just couldn't find an example with a right wall, but if it'd be there, it would work just the same way.

Anyways, as you can see, in this case, we must draw 0,0,1 here after our agent, which is either in 0,0,0 or 1,0,0. However, agent must be drawn after walls in 1,0,0 and ground in 1,0,0, so the agent must be drawn in 1,0,0

So in this case, draw order is:
...
1,0,0
...
0,0,1

Which leads me to believe this cannot be handled in our current tile engine. I think we will require a proper z-level algorithm that draws everything as it would in a 3D game - object after object, based on which object is in front of which. And when drawing limited by layers (like, up to layer 3 or only layer 2), it would just skip objects not belonging to the limit.

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #21 on: October 14, 2016, 05:27:50 pm »
also we have an error in language strings. Delay string for explosives reads msgid "Delay = %i" however it should be float as delay is in increments of 0.25, and it's missing "s." in the end
« Last Edit: October 15, 2016, 08:58:22 am by Istrebitel »

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #22 on: October 18, 2016, 04:33:51 pm »
LINE OF SIGHT

Well I've been thinking on this problem for some time now. Still can't figure out an elegant solution. I didn't look how OpenXCom did it, but we will probably need a different algorithm anyway. In OpenXCom, you only need to update one unit at a time (or update all units once after explosion happens or turn ends and smoke changes). Here we have to update constantly.

Vanilla seems to have updated vision only on certain intervals. It's often a case of agent walking into a new room and seeing nothing, and then after a second or two seeing way more, including enemies that were right up his nose. In such case pausing was benefitial, waiting for the game to update LOS, to see if enemies are spotted.

Anyways, anyone has any ideas how to implement this?

I could of course shoot rays in a frontal cone every X ticks and see which tiles it passed through and check them as "visible", ignoring units (but adding every unit that was passed through to the "visible units" list. But that looks like VERY unoptimal algorithm.

Otherwise, I could shoot a ray to every enemy unit in a frontal cone in a max view distance, and then check if ray hits an obstacle, and how many vision imparing hazards are in the way (smoke). Again, when having many units, that probably would be WAY too expensive. And then again we need to somehow check what terrain do we see.

Offline kkmic

  • Jr. Member
  • **
  • Posts: 61
  • Undefined
    • View Profile
Re: Battlescape progress and questions
« Reply #23 on: October 24, 2016, 03:03:27 pm »
Yeah, the turn-based mechanic simplified the "when" in vision checks for OXC.

Still, doing vision checks all the time will result in lots of wasted cycles, so I tend to incline to an event-based solution (similar to OXC).

Basically, you keep a list of tiles in the agent's view, and then when an event happens, first check if it's in one of those tiles and then:
  • if it's a "terrain" event (destroyed tiles, falling floors?, doors that open/close, agents change tile/position) then update the tiles list and visible entities in the tiles
  • If it's a "entity" event (aliens change tile, weapon bolt changes tile, smoke generated/dispersed), then change the visibility of affected entities accordingly (for example, taking smoke/gas into account)

Easier said than done, I know, but by going with the periodic visibility checks you both waste processor power and provide a sub-optimal experience (just like the original Apoc did).
I've... seen things you people wouldn't believe. Attack ships on fire off the shoulder of Orion. I watched c-beams glitter in the dark near the Tannhäuser Gate. All those... moments... will be lost in time, like tears... in... rain. Time... to die...

Offline Solarius Scorch

  • Global Moderator
  • Full Member
  • *****
  • Posts: 195
  • Call to Power modder
    • View Profile
Re: Battlescape progress and questions
« Reply #24 on: October 27, 2016, 10:20:53 am »
You might want to look at the OXCE+ version of Openxcom, as it modified vision checks, gaining huge FPS improvement with preserved functionality. I don't know the code though, or if it'll be useful.

Offline JonnyH

  • Official Developer
  • Full Member
  • *
  • Posts: 152
    • View Profile
Re: Battlescape progress and questions
« Reply #25 on: October 27, 2016, 10:24:02 pm »
I kinda dislike the non-determinism of 'time based' sight checks, they're not directly related to user input, so feels like you're not really in control. Better to have something that directly triggered by ingame actions - like a unit entering a new tile, or all units within $RADIUS to be updated when a scenery tile is removed (not sure how this would interact with falling tiles though, are they instantly considered 'see through' when they start falling?).

As for the vision checks being expensive, there's lots I can do to make the voxel map checks faster in the future, so there's plenty in the bag if it's a 'bit slow' now it should be relatively easily improved.

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #26 on: November 06, 2016, 08:02:58 am »
Well, I tried multiple improvements and speed was still not optimal. And then I ran Apoc and it dawned to me that Apoc never worked the same as UFO 1&2 do! Lol. I forgot about it completely.

Apoc does not vision check to individual tiles, Apoc does checks to LOS blocks only. You can either see whole block or nothing. That is obviously way faster. We just try to "see" into every block (collision check using LOS loftemps) that is in our field of vision and view distance. If we can reach inside, we see whole block.

Units, then, we check individually. Again, we collison check to every unit within our FOV and distance.

Implementing it that way made algorithm WAY faster and now it's working fine.

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #27 on: November 06, 2016, 09:15:40 am »
Anway, LOS calculations are working fine now, and we have a much bigger problem that needs solving.

Pathfinding in battlescape

After I have implemented patrol AI, I confirmed my suspicions, that unfortunately, our A* does not suffice in the battlescape's complex landscape. Simpliest example is that on every UFO map, aliens trying to exit UFO to patrol have to make a detour to leave through the door, which is often a big detour in terms of comparing path length to a direct line. This makes A* try all sorts of ways of bumping into UFO walls, looking for a faster way which is not there.

Therefore, we must change our pathfinding algorithm for battlescape. Original game used LOS blocks and I assume we should do. I have an idea, but I'd like to hear if someone else has a better one.

I think we should create a weighted graph, four graphs in fact, for walker/flyer and small/large units. The graph's verticles are LOS blocks, while edges are showing which blocks are connected to each other. Edge's weight is amount of tiles it takes to travel from block to block.

When pathfinding, we should first pathfind using A* on the relevant graph (based on unit type). After we know which LOS blocks we have to go through, we go through these blocks, pick a position in every LOS block that is closest to goal and path to it using current algorithm. This way we end up with a somewhat optimal path to destination

Offline Istrebitel

  • Official Developer
  • Jr. Member
  • *
  • Posts: 58
    • View Profile
Re: Battlescape progress and questions
« Reply #28 on: November 24, 2016, 07:00:02 pm »
I guess at least someone's going to be glad to know that I've managed to implement an improved pathfinding algorithm for battlescape, one that uses LOS blocks to navigate greater distances. It needs further improvement of course, but right now it's at least correctly working and working very fast too (no noticeable slowdowns no matter the distance). Here's a small demo (audio is shit, soz):

https://www.youtube.com/watch?v=l_z6YfNbvyU&feature=youtu.be

Offline pmprog

  • Administrator
  • Full Member
  • *****
  • Posts: 175
    • View Profile
Re: Battlescape progress and questions
« Reply #29 on: January 04, 2017, 08:51:35 am »
Damn Istrebitel... I'm well behind in your battlescape work. Need to try and find some time and read most of this thread!

 

hogan outlet hogan outlet hogan outlet woolrich outlet hogan outlet woolrich outlet Nike Air Max Outlet Online replica ray ban outlet moncler outlet peuterey outlet giuseppe zanotti pas cher louboutin pas cher Zanotti Pas Cher nike air max pas cher Moncler Pas Cher cheap nike air max 90 louboutin outlet cheap nfl jerseys from china cheap jordans for sale louboutin pas cher air jordan pas cher lancel pas cher ralph lauren pas cher Sac Longchamp Pas cher ralph lauren pas cher