离散空间等离子射线碰撞轨迹求解算法技术咨询

游戏核心设定 #

• 我正在开发一款搭载等离子枪的游戏，场景为离散棋盘格空间，每个格子可包含等离子枪、等离子射线或无物体。
• 射线支持8个方向（N/NE/E/SE/S/SW/W/NW）的直线或对角线传播，且为瞬时传播，无需时间。
• 碰撞规则：两条射线碰撞时，各自向远离对方的方向偏转90°。

核心需求 #

需要计算满足所有约束条件的所有射线的完整轨迹。目前尝试逐步推进射线传播，但检测到碰撞时需要回溯至碰撞点重新计算，希望得到合适的算法建议。

现有伪代码定义 #

type Dir = N | NE | E | SE | S | SW | W | NW
type RayElem = {x: Int, y: Int, dir: Dir} 
type Ray = [RayElem]

-- 推进所有射线一步
propagateAll :: [Ray] -> [Ray]
propagateAll = ...

-- 推进单条射线一步
step :: [RayElem] -> [RayElem]
step = ...

-- 检测射线元素是否与其他射线碰撞
checkCollision :: RayElem -> [Ray] -> Boolean
checkCollision = ...

现有疑问 #

• 当前用列表存储射线，是否应该改用以碰撞点为节点的图结构？
• 希望了解相关的算法类别或研究方向，用于解决这类带约束的轨迹计算问题。

补充场景说明 #

• 连锁碰撞反应：发射红色等离子枪后，红蓝射线碰撞引发轨迹偏转，进而影响绿色射线的轨迹，甚至会触发更多连锁碰撞。
• 悖论场景：存在射线轨迹互相制约，无法找到合法解的情况。
• 非平凡解场景：存在多种满足所有约束条件的合法轨迹解。

内容的提问来源于stack exchange，提问作者cdupont