• There is NO official Otland's Discord server and NO official Otland's server list. The Otland's Staff does not manage any Discord server or server list. Moderators or administrator of any Discord server or server lists have NO connection to the Otland's Staff. Do not get scammed!

[discussion] isSightClear development discussion thread

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,127
Solutions
20
Reaction score
2,267
Location
Poland
GitHub
Zbizu
Hello.

If you regularly browse issues and pull requests of master branch you probably know about problems with isSightClear function (responsible for throwing items and attacks, ranged monster behaviour, and obstacle detection in area spells). Because all three problems are related to each other and there are already lots of PRs and issues referenced, I decided to post here instead of opening yet another one in github repo or causing unnecessary noise in existing PRs/issues.

I believe that all three problems can be fixed by reimplementing the isSightClear function.
I also believe that area spells could be slightly easier to process if we skip already checked tiles (will discuss that later in this post).


Summary of current problems:
1. isSightClear is far from rl (this is huge issue when a pvp fight happens in a narrow diagonal cave)
  • this causes throwing items and distance attacks different (also applies to area spells although the difference isn't big here)
  • this also causes weird positioning of ranged monsters during combat

2. There is some problem with area spells (they can't be cast in some scenarios)
- although I'm not entirely sure what is causing it, one of possible reasons for that might be weird behaviour of isSightClear when the points A and B are next to each other (eg. 1000,1000 and 1000,1001). Places to look at: combat.cpp, methods: Combat::doCombat(the one with caster, position params) and AreaCombat::getList


A quick rundown on the progress in developing the solution:
  • A potential solution for accurate lines of sight in a single floor: using xiaolin wu's algorithm
  • Early implementation with the consideration of throwing items between floors: link to pr
  • Code improvements and further research in Gigastar's PR, more suitable for tfs standards plus some corrections: link to pr
  • Continued research, small fixes and slightly more specific functions in MillhioreBT's PR: link to pr (sorry for abandoning the early code, I lacked time to work on it. I'm glad you all continue working on it though)

Now that the code is close to being finished, I've noticed the area spells performance could be improved in the future as well (image version here):
  • current area spells call isSightClear to every tile (notice the loop above this line)
  • a new function, something like getSightLine could be written to obtain the path between two points
  • an empty matrix could be used to draw obstacles and their shadows (between caster and most remote points) on it
  • a matrix with spell area could be used to compare it with the shadows to figure out available tiles
  • not really sure of it, but I have a feeling that this could even use gpu acceleration for vector operations assuming someone is turbobrain enough to code it
 
OP
zbizu

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,127
Solutions
20
Reaction score
2,267
Location
Poland
GitHub
Zbizu
current problem of area spells:
  • let's say you cast ue
  • every single tile from spell area calls isSightClear

this means that tiles in exori range for ue spell call tile:hasFlag 4 or more times for a single cast

I've wrote a map generator in the past and one of concepts for it was copying existing fragment of map to use in generated area. The slowest part was accessing the data from the tiles. This is also why I dropped that idea the moment a huge lag hit my testing server.

I propose this solution:
  • scan area once to generate a matrix with obstacles
  • call checks for line of sight locally
  • skip already checked tiles

proof of concept:

edit: "final area" in linked code is the area the spell will avoid
 
OP
zbizu

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,127
Solutions
20
Reaction score
2,267
Location
Poland
GitHub
Zbizu
To sum that up: three areas that could be optimized for area combat have been discovered.

1. isSightClear checks every tile on its way for the flags. Every tile calls isSightClear (some tiles are overlapping wasting the server performance).

2. Every magic effect calls getSpectators within game screen range from itself. This means that every magic effect checks for all players in the screen. To do that... all the tiles get scanned again wasting server resources again, but there's more:

3. Tile combat is in a for loop which sends two things: hp bar update+hit animation and magic effects corresponding to it(hit animation, leech, blockhit, crit animation). Both functions call getSpectators again and if there are many creatures in a single tile, it sends the effects for every player that was hit, to every player in screen range wasting server resources again. So in short: if you have 8 players in a single tile and they get hit by area spell and the spell crits + life leech on everyone, there are 32 animations (8 hp bar updates, 8 magic effects, 8 crit animations, 8 life leech effects) that are sent to all players in screen range. Every single one of them will call getSpectators to see who is in screen range and the combat system was like that for YEARS. Area combat is done this way since at least yurots (so roughly 15 years).

solution: gather tiles from spell area + screen range (+11 tiles extra vertically and +11 horizontally on each side of spell area using viewport constants) once and perform all calculations locally. A vector of spectators could be passed to next function to save time and resources. Tile combat could update hp bars and count magic effects that happened on the tile before sending them so the duplicates would be ignored. Also: tiles from outside of spell area could be freed from memory before looping through spectators to optimize it even more.

Poorly written area combat plus login/logout bottleneck (or load/save players to be exact) is why tfs engine runs poorly with 1000+ online.
 
Last edited:
OP
zbizu

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,127
Solutions
20
Reaction score
2,267
Location
Poland
GitHub
Zbizu
isSightClear reference for developers:
  • throwing to lower floors is only allowed when there is no obstacle on your floor (you can't mix throwing over an obstacle with throwing to lower floor)
  • the shaft above target has to be clear if the target is on the floor below you
  • there is no limit of floors passed when throwing to lower floors
  • throwing to higher floors is only allowed when there is no obstacle on target floor
  • you can throw to +1, but not to +2 or higher
  • magic wall is an obstacle too
 
OP
zbizu

zbizu

Legendary OT User
Joined
Nov 22, 2010
Messages
3,127
Solutions
20
Reaction score
2,267
Location
Poland
GitHub
Zbizu
Top