Roguelike???????

??

?????????????????????????

Roguelike Vision Algorithmswww.adammil.net

??????????????????implementations????

??

??Roguelike?????????????????????????????????????????????????????????????????????????????????????????????????????????

???????/ field of view / FOV?????????????????????????????????tiles??????????�??tile�???/ line of sight / LOS??????????�??tile????�???????????????????????�?????�????/ line of targeting / LOT??

???????

??????????????????????????????????????????????????

• ????Symmetry?? ????tile A?????tile B?????tile B????????tile A????????????????????????LOS?LOT????????????????????????
• ?????Expansive Walls????????????????????????????????????????????????????????????????????????????????????????????
• ??????? ?????????????????????????????????????????????????????roguelike?????????????????????
• ????? ?????????????tile???????????????????????????????????????????????????????????tile???????????????????????????????????????????????????????????????????????
• ?????Artifacts?? ?????????????�??�??????????????????????????????????????????????????????????????????????????????????????????????bug?
• ??? ?????????????????????????tile?
  

????

???????????????

?????Ray casting?

??? ???????????????????????????

??? ????????????????????????

??????????????????????????????????????????????????Bresenham'???[0]?????????????????????????????????????

• ???? Bresenham????????????????????????????????????????????????????
• ????????????????????????????????????????????????????????????
• ???????tile????????????????????????????????????
  

??????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????4?????????????????????????????????????

???http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#raycode

???????tile?????? Shadow casting?

????????????????????????

???????????????????????????????????????????nontrivial??

??????????????????????????????????????????????????????????????????????????????tile????????????tile???????????????????????????????????????????????????????????????????????????? �????�????????????????????????????�Light casting�?�Ray casting�???????????case????????????tile?????????????

??????????????tile?????tile???????????????????tile????????????????????????????????? ??????????????????

???45????????45???????????????????????????????????0?1??????????????????????????????????????????tile???????????????????????????????????

??????????????????????????>>??????????????

????????>>???????????????

??????????????????????????????????????????????????????>????????????

?????????????????????tile??

????????????????????????????????LOS==LOT?????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????LOS????LOT??????????�??????�???????????????????????????

??????????????????????????????????????????????tile?????tile????????tile??????????????????????tile??????????????????????????

???http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#shadowcode

?key point is the strategy of how to determine a tile is visible: just need the sector cover the tile? or need to cover the center point? or cover a certain percentage of area? ?????????????????????????????????????????

????Diamond walls????tile?????

????????????????????????????????

??????????????????????????????????????????

??????????????tile??????tile???????????????????tile????????????????????????????????????????????????????????????????????????tile?????????????????????????? ??????????????????????????????????????????tile???????????????

??????????roguelikes???????????roguelikes????????????????????????????????????????????????????????????????????????? ????????????????????????

?????????????????????????????????????????tile????????????????????????????????????????????????????????????????????

??????????

??????????????????????????????????

???http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#diamondcode

????Half-width walls?

???? ??????????????????

??????????????????????????????????????tile??????????????????????????????????????????????????? ???????????????????????????????????????

???FOV?Permissive field of view??tile to tile?

??? ???????????????????

??? ????????????????????????

?????tile????????tile??????????????????????tile???????????????????????????????????????????????????????????????????????????????????????????????????Jonathon Duerig[1]?????????????????????????????????????????????????????????????????????????????????????

??????????????????????permissivity??????????????????????????????????????????anyway?

??? http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#permissivecode

Digital FOV?????

?????? ???FOV?????

Digital FOV???tile?????????????????????????????????????????????tile?????????????FOV?????????????????? ????????????????????????????????????digital straight line segments????????????? One interesting feature of the algorithm is that the knowledge of the digital line segment from a line-of-sight calculation allows easy tracing of a projectile path through space without hitting any walls, even down somewhat twisted tunnels (such as the Kuo corridor above) ??????????????

????

???????????????ray casting?????????????????????????ray casting????????????????????????????

• ????????????
• ???????
• ?????????????????????????????
• ?????????????
• ????????????????????
• ???????????
• ?????????
• ????
• ????
• ?????
  

????????????????????? ?????2???????????????????????????????????

1.        ?????tile???????????????????

2.        ??????????????tile???

3.        ???????????size???tile?1/2???????tile???

4.        ????????????????????????

????????????????????????????????????????????????????????????tile??????????????????????????????????????

?2??????????????????????????????????????????????????????tile???????????????????????????????????????????tile??????????????????????????????????tile????????????

???????????????????????????????????????????????????tile???????????????????????????????tile???1/2???????????????3/8??????????????????????????????????????????????????????????????1 /2????????????????????????????tile???????????????

?????????1/2???

?????????????????????????????????????????????????????

???????????????????????????????????????????????????????????????????

???????????????????????????????????????????????FOV???????????????????

???http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html#mycode
[0] Bresenham's algorithm: https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm
[1]Jonathon Duerig: https://user.xmission.com/~tyrecius/

?????
?????https://zhuanlan.zhihu.com/p/94699665