Jump to content
  • Advertisement
Sign in to follow this  
Pintrix

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

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement

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 this post


Link to post
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 sad.png ). 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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
  • Advertisement
  • Popular Tags

  • Similar Content

    • By D34DPOOL
      Edit Your Profile D34DPOOL 0 Threads 0 Updates 0 Messages Network Mod DB GameFront Sign Out Add jobEdit jobDeleteC# Programmer for a Unity FPS at Anywhere   Programmers located Anywhere.
      Posted by D34DPOOL on May 20th, 2018
      Hello, my name is Mason, and I've been working on a Quake style arena shooter about destroying boxes on and off for about a year now. I have a proof of concept with all of the basic features, but as an artist with little programming skill I've reached the end of my abilities as a programmer haha. I need someone to help fix bugs, optomize code, and to implent new features into the game. As a programmer you will have creative freedom to suggest new features and modes to add into the game if you choose to, I'm usually very open to suggestions :).
      What is required:
      Skill using C#
      Experience with Unity
      Experience using UNET (since it is a multiplayer game), or the effort and ability to learn it
      Compensation:
      Since the game currently has no funding, we can split whatever revenue the game makes in the future. However if you would perfer I can create 2D and/or 3D assets for whatever you need in return for your time and work.
      It's a very open and chill enviornment, where you'll have relative creative freedom. I hope you are interested in joining the team, and have a good day!
       
      To apply email me at mangemason@yahoo.com
    • By davejones
      Is there a way to automatically change the start position of an animation? I have a bunch of animations set up on 3D models in unity. The issue is that I need to move the 3D models, however when I do so the animation start positions are not updated and I have to do it manually.

      Changing the transform of key frames is time consuming with the amount of animations I have, so I was wondering if there was a way to do it automatically?
    • By MoreLion
      hey all! We are looking for members for our Unity horror game! 
      Here’s the story:
      After a deadly virus plunges the world into chaos killing 85% of the human population there are now what they call “zones” these zones are watched very closely by the surviving government, people are checked every day for the virus, even if you touch the spit or any human waste or fluids of the victim who is infected, you will die. But one day, people in the west zone start to go missing, 1 woman goes outside the walls to uncover the mystery, is there more to the virus than meets the eye?, That is where your story starts.
      This game is not a long development game, I have loads other game ideas,
      I will also allow you to have a bit of creative freedom if you wish to add or share a idea!
      And no, it’s not a zombie game lol I feel like zombie games are too generic, in this game you will encounter terrifying beasts!
      There is some concept art one of our concept artists have made
      If interested email liondude12@gmail.com
    • By Canadian Map Makers
      GOVERNOR is a modernized version of the highly popular series of “Caesar” games. Our small team has already developed maps, written specifications, acquired music and performed the historical research needed to create a good base for the programming part of the project.

      Our ultimate goal is to create a world class multi-level strategic city building game, but to start with we would like to create some of the simpler modules to demonstrate proof of concept and graphical elegance.

       

      We would like programmers and graphical artists to come onboard to (initially) create:

      A module where Province wide infrastructure can be built on an interactive 3D map of one of the ancient Roman Provinces.
      A module where city infrastructure can be built on a real 3D interactive landscape.
      For both parts, geographically and historically accurate base maps will be prepared by our team cartographer. Graphics development will be using Blender. The game engine will be Unity.

       

      More information, and examples of the work carried out so far can be found at http://playgovernor.com/ (most of the interesting content is under the Encyclopedia tab).

       

      This project represents a good opportunity for upcoming programmers and 3D modeling artists to develop something for their portfolios in a relatively short time span, working closely with one of Canada’s leading cartographers. There is also the possibility of being involved in this project to the point of a finished game and commercial success! Above all, this is a fun project to work on.

       

      Best regards,

      Steve Chapman (Canadian Map Makers)

       
    • By Scouting Ninja
      So I have hundreds of moving objects that need to check there speed. One of the reasons they need to check there speed is so they don't accelerate into oblivion, as more and more force is added to each object.
      At first I was just using the Unity vector3.magnitude. However this is actually very slow; when used hundreds of times.
      Next I tried the dot-product check:  vector3.dot(this.transform.foward, ShipBody.velocity) The performance boost was fantastic. However this only measures speed in the forward direction. Resulting in bouncing objects accelerating way past the allowed limit.
       
      I am hoping someone else knows a good way for me to check the speed with accuracy, that is fast on the CPU. Or just any magnitude calculations that I can test when I get home later.
       
      What if I used  vector3.dot(ShipBody.velocity.normalized, ShipBody.velocity)?
      How slow is it to normalize a vector, compared to asking it's magnitude?
    • By Ds ds
      Hi, my name is Andres, I'm a programmer with a technician degree and a Diploma in C#, looking for a project in Unity to start my career in game development. I don't do it for a paid but a recognition and start a portfolio, preferably a 2D game. Thanks for read, have a nice day. 
       
    • By Victor Rodriguez
      Hi there! Is the first time that I'm posting here so I'm sorry if I'm doing it wrong ha. 
      So here it comes, my doubt is, I'm doing a game with different levels, each of these levels in one different scene. Each scene contains to cameras that you can change pressing a button. Everything works fine. 
      The only problem is that I would like it to look a bit more professional, and I would like that if you finish the level with camera2, the next level start the same way. I've been thinking about using dontdestroyonloadon both cameras, but obviously this cameras need to be attached to the player to make the movement work, what do you recommend? Sorry If I've explained it in a messy way, and feel free to dm me for anything. Thanks in advance! 
    • By Ike aka Dk
      Hello everyone 
      I am a programmer from Baku.
      I need a 3D Modeller for my shooter project in unity.I have 2 years Unity exp.
      Project will paid when we finish the work 
      If you interested write me on email:
      mr.danilo911@gmail.com
    • By markoal
      Hi,
      I'm Unity developer from Croatia and I'm looking to work on the paid project in my spare time.
      I have 5+ years of experience in Unity and I'm familiar with almost anything, including all platforms (also Switch, PS4 and Xbox).
      Feel free to contact me.
    • By bartekm777
      Hello
      About me
      Lvl 28   Programmer (day job: non-gamedev-programmer, making games as a hobby for about 2 years) Some vector art experience - tried to make some assets on my own using vector software and scripts   Some design experience (designing my own games ) About game
      Turn-based fantasy rpg inspired by games like Heroes 3 (also WoG mod), NEO Scavenger, Battle Brothers I would like to create easy to use editor for creating custom scenarios (similar to the one from Heroes 3) World and story are clean slate, I did some drafts but I'm not good at it so it's possibly subject to change I decided to create graphics using vector software + scripts to make it faster (rpg's tend to have lots of assets), also it's more precise and easier to create tileable graphics (for example: rivers, paths) No sound/music work has been done yet Who do I look for?
      Definitely someone with 2d art skills  I would like to focus more on programming 2D animator (skletal animations are preferred) Additional programmer could make development faster Someone for creating sounds/music/both It's a hobby project, I work on it in my free time. In case the project make it to the finish line and get shipped  - I can offer rev-share  
      Below should be few screens of what I already did (about 2 months of work) - some graphics, editor prototype screenshot and game prototype screenshot




  • Advertisement
  • Popular Now

  • Forum Statistics

    • Total Topics
      631354
    • Total Posts
      2999499
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!