在游戏开发或网页设计中，常常需要在画布上随机放置多个精灵（如游戏角色或装饰物），而这些精灵之间不能有任何重叠。最近，我遇到了一个问题：使用递归方法来避免精灵重叠时，程序很快就达到了最大调用栈大小，导致无法处理较多的精灵（如15个以上）。此外，精灵的位置倾向于集中在画布的左上角，导致大量的碰撞问题。以下是我在解决这些问题时的一些优化技巧和实例。
问题分析
最初的代码如下：
constgetLocation=()=>{letx=Math.floor(myrng()*(canvas.width-80));lety=Math.floor(myrng()*(canvas.height-80));x=x<0?0:x;y=y<0?0:y;constoverlap=entities.some((entity)=>{return(x-entity.position.x<80||y-entity.position.y<80);});if(!overlap){return[x,y];}else{returngetLocation();}};优化思路
避免递归，采用循环：
- 递归可能会导致堆栈溢出，尤其在高密度精灵布局下。通过循环来代替递归，可以控制循环次数，避免无限递归。
functiongetLocation(){letx,y,overlap;letattempt=0;constmaxAttempts=1000;// 设置最大尝试次数do{x=Math.floor(myrng()*(canvas.width-80));y=Math.floor(myrng()*(canvas.height-80));x=x<0?0:x;y=y<0?0:y;overlap=entities.some((entity)=>{returnMath.abs(x-entity.position.x)<80&&Math.abs(y-entity.position.y)<80;});attempt++;}while(overlap&&attempt<maxAttempts);if(attempt===maxAttempts){console.warn('Could not find a free position after '+maxAttempts+' attempts.');returnnull;// 返回null表示无法找到位置}return[x,y];}改进重叠检测逻辑：
- 原来的重叠检测逻辑存在缺陷，导致精灵倾向于集中在左上角。通过更精确的检测，可以避免这种问题。
预计算空位：
- 如评论中所提，预先计算画布上的所有可能位置，并随机从中选择。这可以大大减少计算量。
// 预计算空位letavailablePositions=[];for(letx=0;x<canvas.width-80;x+=80){for(lety=0;y<canvas.height-80;y+=80){availablePositions.push({x,y});}}functiongetLocation(){if(availablePositions.length===0){console.warn('No more available positions.');returnnull;}constindex=Math.floor(myrng()*availablePositions.length);letpos=availablePositions.splice(index,1)[0];return[pos.x,pos.y];}
实例
假设我们要在一个800x600的画布上随机放置20个精灵：
constentities=[];for(leti=0;i<20;i++){constposition=getLocation();if(position){entities.push({position:{x:position[0],y:position[1]}});}else{break;// 无法找到更多位置时停止}}通过这些优化，我们不仅解决了最大调用栈的问题，还提高了精灵的分布均匀性和程序的效率。这些技巧可以应用于任何需要在有限空间内随机且无重叠放置对象的场景中。
