Java more efficient array search
I am coding a game using LibGdx and I have an array with all my wall objects the player can collide with. For those not using LibGdx, I'm talking about the LibGdx Array class, which provides the same functionality as ArrayList, but is built with memory efficiency in mind. When I check for collision, I need to go through each wall in the array and check for collision like this:
for(Wall w : walls) {
if(w.bounds().contains(player.bounds()) {
// handle collision
}
}
I realized that this was inefficient because I go through every wall, even if that wall is disconnected from the current map view. Obviously, if I am checking for collisions with walls currently in the camera viewport (which means they are currently visible to the player), then there is no point in going through the whole array because the player cannot collide with them until they are will enter the View. I was thinking about making my game a little more efficient by only checking for collisions with walls next to the player. In my game, I have all the walls snapped to a grid with 32x32 px cells. I really don't know how I could create a more efficient clash search. Can I use as a map of some kind that uses the vector2 position for its key,and then scans the player's position and scans the walls in a specific range from the player's position on the map? I just really lost how to have a code that won't go through all 100 walls in my game when there are only 10 current possible walls that the player could touch because of where they are. Does this make sense? Can anyone explain a good way to do something like this? Many thanks.
source to share
There are many collision algorithms, you need to find the one that suits you.
One solution I can think of at the top of my head:
Save a list of your walls, sorted by their coordinates. If you are creating a new wall, use insert sort to apply the pattern. If you want to check for collisions, take the coordinates of the objects (in this case, probably the player who is working) and do a double search to find the nearest wall for the player. Then calculate if the player collides with this wall. If the nearest wall is not causing a collision, you can be sure that there will be no other wall either.
source to share
Each wall sits on one or more of these 32x32px grids. Let the grid coordinates be x and y. If the mesh contains a wall, enter it in
HashMap<CoordPair,Set<Wall>> xy2wall
To explore where a location is in contact with an adjacent wall, use the location coordinates to define a small set of grid coordinates, select the Walls set or sets displayed by those coordinates. I think Player.bounds () can provide a suitable set of coordinates.
If a 32x32 grid results in too many entries, you can always use a coarser grid.
source to share
I once came to the same realization that you have when developing from top to bottom rpg. There are more walls than you can imagine at the top of the page.
This is how I solved it:
First: segment the map into zones, i.e.) draw the map on paper or something and cut it into pieces.
Second: Record the pixel boundaries for each segmented section of the map.
Third: check where your players are in relation to the borders.
Finally: check walls only within these boundaries.
In the realm of endless walls, this is not more efficient (talking about Big O), but for all practical purposes it is effective in reducing search times
if (boundary1.contains(player1)) {
for(Wall w : Boundary1Walls) {
if(w.bounds().contains(player.bounds()) {
// handle collision
}
}
}
else if (boundary2.contains(player1)) {
for (Wall w : Boundary2Walls) {
if(w.bounds().contains(player.bounds()) {
// handle collision
}
}
}
.... continue this way
Note ... I did it this way before going to college for software engineering, so I didn't use data structures like BST that could be used to store walls in relation to their coordinates. Fast search time.
source to share