Comments (2)
Can the operation to determine what zones collide with a grid cell be improved by sorting the zones by their y coordinate at the start, and then using binary search to find the starting point to start testing zones based on their "minimum y", which would be their y - radius
and stopping at their "maximum y" which would be y + radius
?
from polyzone.
The binary search, while smart, didn't work out because of something I missed when originally thinking about it. Sorting by the Y position then using binary search to the "minimum y" or "maximum y" doesn't work, because zones can have different radii. Therefore you could get to a zone that is outside the grid row, even if the zone after it is inside the row, or vice versa.
So instead, I just precompute and cache the zones in each row by doing the check at ComboZone creation, or whenever the AddZone method is called. This actually runs about as quickly as the sort necessary to do the binary search method, but removes the runtime cost of the search.
This cache turns the grid into basically a multi-layer spatial partitioning system. The first time the player/point enters a new grid cell, the zones inside of it have to be calculated. To do this, first the grid rows cache is accessed to get all the zones in that row. Then for each zone in the row, a circle to rectangle collision test is done to determine if the zone is in the cell. If it is, it's added to the grid cells table. After the grid cell generation is done, you can then return those zones in the cell to be used by isPointInside().
I chose a grid over a more flexible data structure like a quadtree because it's significantly simpler, avoids lots of table lookups (expensive in Lua), and can be generated on the fly when the user enters a grid cell, rather than all at once. The speedup this offers is roughly the amount of grid cells, minus some overhead. The default grid layout is 34 columns and 50 rows, meaning a speedup of roughly 1700. This assumes your zones are relatively well spaced out, and in reality will likely be cut down a bit due to zones clustering more than the purely even spread that this theoretical maximum speedup assumes. But even if we assume it's only 1000, it's still three orders of magnitude faster.
Commits:
22dca26
6769b81
ae1c3f7
e32dab9
from polyzone.
Related Issues (20)
- QUESTION HOT 2
- Polyzones linking together HOT 1
- Combo onPlayerInOut method not getting triggered HOT 8
- Not an Issue, Vehicle delete outside of Zone
- [QUESTION] Is there any way to edit inside the zone? HOT 1
- scroll down not working when working on zone
- [Potential Bug?] HOT 2
- Warning: Passed points table with less than 3 points to PolyZone:Create () {name=test}
- [HELP] Bug or misunderstanding HOT 1
- Need help on code. HOT 2
- Add support for Javascript or add exports HOT 4
- Problem in isPointInside when use circlezone HOT 1
- pzdebug command HOT 5
- Regarding Issue #90 HOT 2
- pzcreate box HOT 4
- Attempt to index a nil value HOT 1
- attempt to index a nil value
- polyzoones HOT 1
- C#
- REDM BlockWeaponThisFrame - nil value HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from polyzone.