Mapping an area with raycasting

Unity Engine
,
1

I’d like to able to map an area using raycasting.

I want to use it to find all dead ends, turns and exits of a place(like a building or a maze)
I know if I want to exit it I can just use NavMesh, but the reason I’d like to do it this way is so I can wisely select a path which avoids certain things (like enemies)

I know some people would already suggest to make the enemies obstacles but it won’t be all that good for two reasons:

  1. I only want the target to avoid them, not all other agents, and certainly not them from themselves
  2. I don’t just want the target not to touch them, I want the target to run away from them.

The way I thought of mapping a place with raycasting is the following(Image)
Blue dot - you
Black line - wall
Arrows - raycasting
The red arrows are the first raycasting, orange second, yellow third etc. (Recurring task)

the image also displays the two problems I think I’d encounter trying to do so.

Problem 1) Overmapping, I overmapped in the drawing by purpose, most of the arrows are not even needed as the map as already fully revealed, how can I tell when I already mapped it all?

Problem 2) Dead end mapping, the pink arrows are arrows that lead straight to a wall.
There is no need at all to make them, infact, making them will make this method infinite because you can always continue, so I need to know how to avoid making those arrows.
thought it’d be easy, but then another thought and I realized that it isn’t that easy…

I mean just because the distance is short doesn’t mean it’s a dead end, and it can still be raycasted properly, I don’t really know how I can tell the system to avoid it.

Could you please help me think of a way to solve those problems, make your opinion about my solution and perhaps even suggest me with ideas I haven’t thought of?

Appreciating your comments

6468260--725777--Mapping.png
6468260--725777--Mapping.png1200×900 7.73 KB

2

You need to discretize the map space if you want to explore a non-discrete map in an optimal manner.

This means you need some sort of spatial unit that you can mark as explored. Normally such a design allows you to be in charge of algorithm’s accuracy vs complexity trade off.

Once in discrete units, you can apply an algorithm similar to standard flood fill.
Even if you have to do raycasting, at least try and be conservative about it. Raycasting is expensive.

3

I know it is expensive… it’s a problem, but what I did for now is making a threshold for distance to eliminate dead ends, and made a max amount of gens so it won’t over explore, also, this function should only run once per area so I guess I shouldn’t be too worried… also this is what it can do so far(Image)

Also… I keep the final ends open by purpose, this is so I can tell when I find an exit.
tho… as you can see all the points are right near the walls, because it is raycasting to a direction, if it finds a wall it marks the hit.point and does it again for its sides using Vector.Cross, if the cast it way too short (the reason it didn’t cast in the bigger hall to the sides) it will not cast.

Also I assume I could use the position which I save for use to mark exploration altho it’s not that ensuring

6469703--726074--map.PNG

4

Well, if your levels are always orthogonal like this, I would do things wildly differently, but okay you can do it like that if you wish. I would never ever generate a geometry model first, and then scan that back to my internal states, when it’s much simpler to create an internal model first, run whatever algorithm on that, and proceed with generating geometry from what is found to be a solved space.

But fwiw my remark above was related to having any shape of the level, including full 3D.

5

Yeah… you’re right it only works for orthogonal structures… I really need to find an efficient solution for non-orthogonal ones