Best way for enemy searching script

[hkplay]

Hello, I just started making a 2D top down stealth game. Most of the levels will be in buildings, with walls and rooms.

Right now my enemy has a few states, idle, chasing, etc. I have coded out what I want the enemy to do upon seeing the enemy, when chasing the enemy and stuff. I am using NavMeshPlus for 2D pathfinding.

My problem lies in what happens if the enemy lose sight of me (the player). What I want them to do is to start an organized search to go through every part of the map to look for me.

Is there a best way to do this?

My idea now is to maintain a grid as a graph (nodes are squares with trigger colliders…?) on the map. Each enemy will then perform a Breadth-First-Search from their point on the graph to find the closest point that is “not searched” yet, and set a path there. Upon touching any node on the graph, that node will be set as “searched”.

My concern is that this may not be efficient? My game won’t be that big however, my game should only have 60 bots maximum, and the maximum number of nodes at a reasonable size should be 40 x 40 = 1600 nodes for each level. (this is an generous upon bound).

A potential optimization would be to do direct distance comparing if the number of nodes not searched yet is small and BFS might meet a lot of searched nodes already. Another way is maybe to do depth first search to find a reasonably far point so that the path is not updated too often.

The reason I decided on this is because each Bot should search a different place

Another way would be to manually place different points on the map that has to be searched (example, rooms), that way I would be sure that the number of points remain small.

However my main concern is because one of the end goals for the game is to make a level editor as well, where players can design their own levels to share and play. I wouldn’t want the level editor to include placing your own points on the map for the bots to search, so it should have the same “implementation” for all maps.

Thank you for reading this long post. This is my first time making a game and I really intend to finish it. I apologize if I made some rookie mistakes in game design. Right now I am targetting it for PC, but I hope that it could be ported to mobile as well next time.

[mgear]

i guess randomly picking locations around the map wouldnt look realistic?
or they could start patrolling from one end to another? (then sometimes swap to patrolling between northest point to southest…)

or can you somehow detect rooms from the map, is it grid/tile based map?
(then could check for areas that have at least 4x4 floor tiles? same for corridors etc.)

[hkplay]

@mgear

…

Yup I thought it wouldn’t make sense for the bot to search areas that other bots have searched already.

I guess they could patrol from one end to another, but if there were rooms in the middle of the map then they might miss out on it.

Detecting rooms from the map seems ideal, yup i made it tile based.

However currently the floor tiles are like the background (every square on the map has a floor tile), and the walls (gameobjects) are placed over the floors (i am using the 2D tilemap extras package to paint gameobjects like tiles).

I am quite unsure what is the method to determine rooms though. Do you happen to have an idea in mind? Could there be a way get all floor tiles from the tilemap? Or to get all tiles that doesn’t have a wall on it without writing my own script?

Thank you for the quick response

EDIT:
Looks like there is a tilemap.getTile. I will look into how to use it. However I will appreciate any more ideas and help, thank you.

[mgear]

if you are painting, modifying or loading the map,
then at that point you can already have array of tile types, or basically just array of all floor tiles.

Then no need to iterate through map tiles, which could be slower.

room detection,
do you have screenshot how your maps look like?

i guess initially could just try finding any rectangle areas that filled with floor (or walkable) tiles.

[hkplay]

@mgear

…

This is a crude design i just made (don’t mind the big empty space), which i think might be a good representation of rooms? I haven’t really dealt with making good art and levels as I was thinking of making it playable first. I might look for artists online as I can’t really draw.

EDIT: Just want to mention that the map in the picture isabout 40x30 tiles. however I might have a 120x120 tiles map (should be an upper bound)

I have these tiles in my palette, of which only the pinkish tile is a sprite, while the rest are all game objects and need the GameObject brush.

As for navmesh, this is my grid hierarchy. The “Floor” tilemap has a modifier with override “walkable”, while each individual wall (all which are placed as children of the Walls tilemap) has a modifier with override “Not walkable”

Initially I was thinking of finding big open rectangles, but I forgot my game has diagonal walls as well…

One way that I thought of was to just treat any open space that is surrounded by walls to be a room, but I am afraid some places that can be considered a “room” that needs to be searched might not have walls completely surrounding it.

However, I did think of a potential better solution to my graph problem, which is to split the graph up into smaller graphs, thus reducing the number of nodes in a single graph?

So instead of 40x40 nodes, maybe have 10x10 nodes in which each node is 4x4 more smaller nodes. A “big” node is only considered “searched” if every one of its smaller nodes are “searched”.
EDIT: In fact 40x40 was thinking that each “node” is 3x3 tiles, but seems like it can be as large as 5x5 tiles with the room size…

Again thank you for the fast response.