# Unity Making 23040000 linecasts per second might be too taxing for the CPU

This topic is 1507 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello

I'm planning to make a 2D top-down heist game (somewhat similar to Monaco, only you control more than one person at a time) in Unity, with levels consisting of squares.

I made a rough estimate of the size of a level (about 160x160 = 25600 tiles), and of the number of human or computer controlled characters in it at any given time (about 15). Every character will have to calculate its own LoS. Every frame, every character will have to make a linecast to every square, to check whether it's visible or not (if a square is invisible, it will appear a little darker). However, 160x160x15x60 = 23040000 linecasts per second seems a little CPU intensive, therefore I have thought of some solutions:

• Check line of sight once per 1/2 second, instead of once per frame (divides amount of linecasts by 30 (assuming fps=60), bringing it back to 23040000/30 = 768000 linecasts per second (still a lot).
• Don't check in a 360° circle around every person, but only in a 90° or 180° cone. However, this has two disadvantages:
• Assuming the character is standing in the center of the level, it will only divide the number of squares by about 2 to 4.
• Of course, you can set a maximum viewing distance to the cone to further limit the number of linecasts, but that seems a little unrealistic.
• Determining which tiles are part of the cone might even take more CPU power than making a linecast to every tile.
• Before making a linecast to a tile, first check if another person on your team ("human" is a team, and so is "computer") has vision on that tile. There could be a 160x160 twodimensional array humanVisibleTiles, which holds as a bool every square and whether it's visible for the humans or not. Say, for example, that person1 (controlled by the player) has made a linecast to square (40, 117). When person1 has checked all 160x160 squares, he submits his visible tiles, after which the union of person1's visible tiles and humanVisibleTiles will be stored in humanVisibleTiles. Then, person2 comes along, and is about to check (40, 117), but first checks if it is already visible in humanVisibleTiles. It will return true, which means that person2 doesn't have to check that tile at all, thus preventing one linecast. Of course, this solution is only effective if one if clause is less CPU intensive than one linecast, but I'm almost sure that's the case.

I have read through some other threads about raycasting/linecasting and its CPU cost (this thread in particular), and found that not casting lines every frame but at other intervals (my first solution) is the most effective. However, I can imagine that a player peeking around a corner and getting shot by a guard because his LoS updates only twice a second may get frustrated.

I'd like to get this part of the game development tackled, because it's a quite essential part of it. Monaco (and other 2D top-down games) have proven to handle this without demanding too much CPU, but then, Monaco doesn't cast a line to every tile every frame, but instead probably uses an algorithm similar to the one discribed here.

Do you have any tips on performance optimization? Thanks in advance!

##### Share on other sites

Keeping an array of every single tile's visibility from every single other tile would be less than 80 MB (160^4 / 8), so just make a bool tileVisible[srcX][srcY][dstX][dstY] for now. If you actually need to hit a lower memory footprint later, worry about it later. For all you know, you'll change something that will make all of this coding irrelevant before launch anyways. And if you're targeting PC, you won't ever feel like 80 MB for map data is a waste.

##### Share on other sites

Thank you, KulSeran, richardurich, and nfactorial, for your replies!

richardurich:

Yes, I'm planning on releasing this game solely on Windows and Mac, so 80MB of RAM won't be a problem at all, it is the CPU that bothers me (I'm not worrying about graphics, it is a graphically simple 2D game).

nfactorial:

This is in fact a very good solution, until the moment you open or close a door, or break down a wall (yes, there is an engineer with a drill, forgot to say that). As soon as that happens, all precalculations become obsolete, and every tile will have to recalculate their vision to all other tiles (and that would mean 160^4=65536000 calculations during the game ). If there is any other way to use your idea without this effect, please tell me, as I can't think of one.

KulSeran:

If you're doing this on a tile grid as you say, use something like http://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm to trace out a check of only the tiles directly between you and the player ...

I very much like that suggestion! Would it mean that every guard makes a LOS check to the players with a Bresenham line, wich immediately stops as soon as they encounter an obstruction such as a wall? Also, would this be faster than a Unity built-in raycast?

You'd reverse the process every time your flood-fill lighting into a wall tile to block off a possible edge of the shadow.

I'm not sure what you mean by reversing the process, and how that is going to help blocking off a possible edge of the shadow.

If you did ray-casts to every tile, you'd have to start caching the result (which would in turn become like the floodfill, only more expensive) because the farthest away tile checks need to check all the same nearby tiles you're claiming need a separate ray cast.

Why whould I have to cache the result map of the 160x160 raycast? Because it would be hard to access it every (few) frame(s)?

Why do the farthest away checks need to check all the same nearby tiles I'm claiming need a separate ray cast when I'm not using the floodfill method? I'm afraid I really don't get that.

##### Share on other sites

You need a 3-DOP vs BVH or quad tree broad phase with a 3-DOP-to-tile narrow phase.

3 2D planes make a frustum that represents the enemies’ field-of-view.

Broad phase: All tiles are held in a quad tree or BVH.  Simply traverse whichever structure you use without needlessly testing areas clearly not inside the frustum.

Narrow phase: Until you get to the root nodes in which you test tiles themselves.

Tiles not on the screen don’t need to be considered.

Remaining tiles are then ray-traced.

L. Spiro

##### Share on other sites
Why do the farthest away checks need to check all the same nearby tiles I'm claiming need a separate ray cast when I'm not using the floodfill method? I'm afraid I really don't get that.

If you have a character in the center of your map, and you check the 8 tiles surrounding it, and the top 3 tiles are all walls then what? Why would you even bother checking the ~25% of the map in the triangle made from the top left corner of the map to top right to center? you already know that every single one of those ray checks has to fail, it's going to hit the same 3 wall tiles you already ray checked were on the north side of the character. That's ~6400 squares you can mark as "in shadow from character X" after doing those 3 ray casts finding walls, then two lines drawn to mark off the triangle.  But each of those ray casts is "cheap" in that it nearly instantly finds a wall.  The further away the wall, the more tiles you're re-checking with each ray cast.

Look in 1d:

XXXXX*----X

If * is your character, and you "ray cast" every single tile. The ray casts from 1 to 5 all do the same exact check, is 5 clear? no it's a wall. give up.  All the ray casts from 7 to 11 say is 7 clear? ok. is 7 and 8 clear? ok. is 7 and 8 and 9 clear? ok. is 7 and 8 and 9 and 10 clear? ok. is 7 and 8 and 9 and 10 and 11 clear? no. 11's a wall.

Had you just flooded out from the *, 5's a wall stop. 7's clear, 8's clear, 9's clear, 10's clear, 11's a wall stop.

And now back to 2d, notice how, as you fill outward, you can start blocking off triangles of tiles that you no longer need to do ray casts to, because it's not possible to reach them due to already finding a wall. 18 of 81 tiles weren't checked in my diagram, or ~22%. And since I'm flood filling, there were only 8 ray casts to draw the 4 triangle cones for the shadows.

X???????X    X???????X    X???????X    X???????X
?X?????X?    ?X?????X?    ?X?????X?    -X?????X-
??X???X??    ??X???X??    X-X???X-?    X-X???X--
???XXX???    ??-XXX-??    XX-XXX--?    XX-XXX---
???-*-??? -> ??--*--?? -> ?---*---? -> ----*----
???---???    ??----XXX    ?-----XXX    ------XXX
?????????    ??-----X?    ?------X?    -------X?
?????????    ????????X    ?-XXX---X    --XXX---X
?????????    ?????????    ?X??X????    -X??X----

##### Share on other sites

If you are a 2d tile based game, then yes, doing bresenham or just about any other tile operation will be much faster than using Unity's raycast function.  In fact, if you're going for speed and are a 2d tile based game, I wouldn't use unity's raycast much at all.  Unity's raycast function doesn't know that it doesn't need to check every single tile on the map (Unless maybe you were dynamically moving which tiles were on which layers, but at that point you would already know which tiles to check)

Also limited line of sight makes sense for when a level isn't brightly lit, or has fog, or just for hellishly long distances, so a cone isn't a bad idea, especially since it might be very frustrating for a player to get spotted by a guard is who very far away and off the screen.

Edited by ferrous

##### Share on other sites
Also limited line of sight makes sense for when a level isn't brightly lit, or has fog, or just for hellishly long distances, so a cone isn't a bad idea, especially since it might be very frustrating for a player to get spotted by a guard is who very far away and off the screen.

I agree with you. Maybe it's better to give the players (or at least the guards) a maximum viewing distance, to prevent such situations.

KulSeran:

Thanks, I understand the idea now! However, on your 2D example, I encountered a problem. I will be using * for the character, - for empty space, / for an unchecked tile, X for definitely shadow (checked), and O for a tile that is marked as part of the shadow line because of the wall between it and the character.

Given a level as shown in fig 1(without fog or other vision obstruction. Simply the level lay-out), I do not understand the way you cast the shadows behind the edges of a wall. fig 2 shows step 1 in the area scanning process. This step isn't hard to understand, with two lines following from the edges of the wall. However, I don't quite get the second step, where there are two shadow lines, appearing out of a wall tile. How did you decide what direction the shadow lines would be cast in? The same thing goes for the upper-left piece of wall (next to the original 3 tiles wide wall).

     ---------     O///////O     O///////O
---------     /O/////O/     /O/////O/
---------     //O///O//     //O///O//
-X-XXX---     ///XXX///     //-XXX-//
----*----     ///-*-///     //--*--//
------X--     ///---///     //----XOO
---------     /////////     //-----O/
--XXX----     /////////     ////////O
---------     /////////     /////////
fig 1         fig 2         fig 3
lay-out       step 1        step 2


The only thing I can think of is that you decided that for wall tiles that appear alone, like the two cases I mentioned, one or two shadow lines will be drawn, depending on where the wall is positioned relative to the character, as shown in the following table

011123334
F01123345
FF0123455
FFF024555
EEEE*6666
DDDCA8777
DDCBA9877
DCBBA9987
CBBBA9998


In area 0, only one shadow line will be drawn; to the north-west

In area 1, one shadow line will be drawn to the north-west, another to the north

In area 2, only one shadow line will be drawn; to the north

In area 3, one shadow line will be drawn to the north, another to the north-east

In area 4, only one shadow line will be drawn; to the north-east

In area 5, one shadow line will be drawn to the north-east, another to the east

In area 6, only one shadow line will be drawn; to the east

In area 7, one shadow line will be drawn to the east, another to the south-east

In area 8, only one shadow line will be drawn; to the south-east

In area 9, one shadow line will be drawn to the south-east, another to the south

In area A, only one shadow line will be drawn; to the south

In area B, one shadow line will be drawn to the south, another to the south-west

In area C, only one shadow line will be drawn; to the south-west

In area D, one shadow line will be drawn to the south-west; another to the west

In area E, only one shadow line will be drawn; to the west

In area F, one shadow line will be drawn to the west, another to the north-west

For wall tiles not appearing alone, but in together (like most walll tiles will), I suppose that as soon as you find an edge, you continue the Bresenham line between the character and the wall tile, until it exits the level boundaries?

Once again thanks for all your replies!

##### Share on other sites

Yeah, sorry hard to draw in 2d... I'd say, for every tile you discover that is an X, do 4 ray-plane intersections in floating point.  Send a ray from the player's center (eg <3, 20>) to the 4 tile corners (eg. for the tile <2, 2> that'd be <2.5, 2.5> <2.5, 1.5> <1.5, 1.5> <1.5, 2.5>).  You'd end up with 4 lines that intersect at some edge cordinates like <1.95,0>, <1.45, 0>  (assuming i can roughly math...) Round that off to the nearest integer tile centers <1, 0> and <2, 0>, and then do the bernstrum line drawing from <2,2> to <2,0> and <2,2> to <1,0> to draw the shadow edges.

##### Share on other sites

Wouldn't it be easier to only draw two linecasts per wall tile, based on the relative position of the character to the wall, thus halving the number of linecasts? It would take some ifs or a switch to determine the character's area, but everything's better than two extra floating point linecasts, isn't it?

000012222     If the character is standing in area ...
000012222     0 bottom-left and top-right corners are used
000012222     1 top-left and top-right corners are used
000012222     2 top-left and bottom-right corners are used
7777X3333     3 top-right and bottom-right corners are used
666654444     4 bottom-left and top-right corners are used
666654444     5 bottom-left and bottom-right corners are used
666654444     6 top-left and bottom-right corners are used
666654444     7 top-left and bottom-left corners are used


So, to recap:

Every frame, a character loops through several steps of checking his surrounding tiles. Every step his "checking circle" expands by 1 tiles in all directions, starting with his 8 adjacent tiles. Every step, the character checks all tiles in his checking circle.

Is this tile a wall or other vision obstruction?

No:

Go on to the next tile

Yes:

Make a Bresenham from the character to the tile to see if it's in LOS (check if there's a wall or shadow tile in the way)

Not in LOS:

Go on to the next tile

In LOS:

Draw two floating point Unity linecasts from the center of the character tile to the right corners, and see where they intersect with the level boundaries. Round these two intersection points to the nearest tiles, and then draw shadowline Bresenhams towards them from the original wall tile.

Go on to the next tile

When the character is done checking his circle (actually, it's more of a square) for vision obstructions, he then flood-fills all unspecified tiles (i.e. all tiles that are not a wall, and haven't been marked as shadow line), until he has reached his vision border (maximum viewing distance).

All player's characters will then combine their vision and based on that, some tiles will be grayed out (those are shadow tiles), and others will be full bright (those are visible).

I think there may be a more efficient solution, without the use of any linecasts:

Is this tile a wall or other vision obstruction?

No:

Was the previously checked tile a wall?

Yes:

The previously checked tile was a wall edge. Create a Bresenham shadow line from the character to that tile and continue it all the way to the level boundary.

Go on to the next tile.

No:

This is just an ordinary empty tile; go on to the next one

Yes:

Make a Bresenham from the character to the tile to see if it's in LOS (check if there's a wall or shadow tile in the way)

Not in LOS:

Go on to the next tile

In LOS:

Is this the beginning of a wall? (no if the previously checked tile was a wall)

No:

Go on to the next tile (don't draw a Bresenham shadow line because there will be taken care of that on the beginning and ending edges of the wall)

Yes:

Create a Bresenham shadow line from the character to that tile and continue it all the way to the level boundary.

When the character is done checking his circle (actually, it's more of a square) for vision obstructions, he then flood-fills all unspecified tiles (i.e. all tiles that are not a wall, and haven't been marked as shadow line), until he has reached his vision border (maximum viewing distance).

I haven't tested any of it yet, but I think that if the second algorithm is accurate enough (and I sure hope so), it is the one I will go with.

Do you have any suggestions for one or both of the algorithms?

##### Share on other sites

I would think about game world more like round..

start point sight from 0.. 2pi

circle by circle eliminate segments from sight, clever skip tiles that potentialy are alredy covered, clever manage circle checks if most circle is alredy covered and so on....clever data usage 160x160 tiles = 800 ints easy to cache

How complex is your world? How much concave polygons of ~10 lines can be in your world?

Edited by serumas

• 9
• 10
• 12
• 10
• 10
• ### Similar Content

• By GytisDev
Hello,
without going into any details I am looking for any articles or blogs or advice about city building and RTS games in general. I tried to search for these on my own, but would like to see your input also. I want to make a very simple version of a game like Banished or Kingdoms and Castles,  where I would be able to place like two types of buildings, make farms and cut trees for resources while controlling a single worker. I have some problem understanding how these games works in the back-end: how various data can be stored about the map and objects, how grids works, implementing work system (like a little cube (human) walks to a tree and cuts it) and so on. I am also pretty confident in my programming capabilities for such a game. Sorry if I make any mistakes, English is not my native language.
• By Ovicior
Hey,
So I'm currently working on a rogue-like top-down game that features melee combat. Getting basic weapon stats like power, weight, and range is not a problem. I am, however, having a problem with coming up with a flexible and dynamic system to allow me to quickly create unique effects for the weapons. I want to essentially create a sort of API that is called when appropriate and gives whatever information is necessary (For example, I could opt to use methods called OnPlayerHit() or IfPlayerBleeding() to implement behavior for each weapon). The issue is, I've never actually made a system as flexible as this.
My current idea is to make a base abstract weapon class, and then have calls to all the methods when appropriate in there (OnPlayerHit() would be called whenever the player's health is subtracted from, for example). This would involve creating a sub-class for every weapon type and overriding each method to make sure the behavior works appropriately. This does not feel very efficient or clean at all. I was thinking of using interfaces to allow for the implementation of whatever "event" is needed (such as having an interface for OnPlayerAttack(), which would force the creation of a method that is called whenever the player attacks something).

Here's a couple unique weapon ideas I have:
Explosion sword: Create explosion in attack direction.
Cold sword: Chance to freeze enemies when they are hit.
Electric sword: On attack, electricity chains damage to nearby enemies.

I'm basically trying to create a sort of API that'll allow me to easily inherit from a base weapon class and add additional behaviors somehow. One thing to know is that I'm on Unity, and swapping the weapon object's weapon component whenever the weapon changes is not at all a good idea. I need some way to contain all this varying data in one Unity component that can contain a Weapon field to hold all this data. Any ideas?

I'm currently considering having a WeaponController class that can contain a Weapon class, which calls all the methods I use to create unique effects in the weapon (Such as OnPlayerAttack()) when appropriate.

• Hi fellow game devs,
First, I would like to apologize for the wall of text.
As you may notice I have been digging in vehicle simulation for some times now through my clutch question posts. And thanks to the generous help of you guys, especially @CombatWombat I have finished my clutch model (Really CombatWombat you deserve much more than a post upvote, I would buy you a drink if I could ha ha).
Now the final piece in my vehicle physic model is the differential. For now I have an open-differential model working quite well by just outputting torque 50-50 to left and right wheel. Now I would like to implement a Limited Slip Differential. I have very limited knowledge about LSD, and what I know about LSD is through readings on racer.nl documentation, watching Youtube videos, and playing around with games like Assetto Corsa and Project Cars. So this is what I understand so far:
- The LSD acts like an open-diff when there is no torque from engine applied to the input shaft of the diff. However, in clutch-type LSD there is still an amount of binding between the left and right wheel due to preload spring.
- When there is torque to the input shaft (on power and off power in 2 ways LSD), in ramp LSD, the ramp will push the clutch patch together, creating binding force. The amount of binding force depends on the amount of clutch patch and ramp angle, so the diff will not completely locked up and there is still difference in wheel speed between left and right wheel, but when the locking force is enough the diff will lock.
- There also something I'm not sure is the amount of torque ratio based on road resistance torque (rolling resistance I guess)., but since I cannot extract rolling resistance from the tire model I'm using (Unity wheelCollider), I think I would not use this approach. Instead I'm going to use the speed difference in left and right wheel, similar to torsen diff. Below is my rough model with the clutch type LSD:
speedDiff = leftWheelSpeed - rightWheelSpeed; //torque to differential input shaft. //first treat the diff as an open diff with equal torque to both wheels inputTorque = gearBoxTorque * 0.5f; //then modify torque to each wheel based on wheel speed difference //the difference in torque depends on speed difference, throttleInput (on/off power) //amount of locking force wanted at different amount of speed difference, //and preload force //torque to left wheel leftWheelTorque = inputTorque - (speedDiff * preLoadForce + lockingForce * throttleInput); //torque to right wheel rightWheelTorque = inputTorque + (speedDiff * preLoadForce + lockingForce * throttleInput); I'm putting throttle input in because from what I've read the amount of locking also depends on the amount of throttle input (harder throttle -> higher  torque input -> stronger locking). The model is nowhere near good, so please jump in and correct me.
Also I have a few questions:
- In torsen/geared LSD, is it correct that the diff actually never lock but only split torque based on bias ratio, which also based on speed difference between wheels? And does the bias only happen when the speed difference reaches the ratio (say 2:1 or 3:1) and below that it will act like an open diff, which basically like an open diff with an if statement to switch state?
- Is it correct that the amount of locking force in clutch LSD depends on amount of input torque? If so, what is the threshold of the input torque to "activate" the diff (start splitting torque)? How can I get the amount of torque bias ratio (in wheelTorque = inputTorque * biasRatio) based on the speed difference or rolling resistance at wheel?
- Is the speed at the input shaft of the diff always equals to the average speed of 2 wheels ie (left + right) / 2?
• By Estra
Memory Trees is a PC game and Life+Farming simulation game. Harvest Moon and Rune Factory , the game will be quite big. I believe that this will take a long time to finish
Looking for
Programmer
1 experience using Unity/C++
2 have a portfolio of Programmer
3 like RPG game ( Rune rune factory / zelda series / FF series )
4 Have responsibility + Time Management
and friendly easy working with others Programmer willing to use Skype for communication with team please E-mail me if you're interested
Split %: Revenue share. We can discuss. Fully Funded servers and contents
and friendly easy working with others willing to use Skype for communication with team please E-mail me if you're interested
we can talk more detail in Estherfanworld@gmail.com Don't comment here
Thank you so much for reading