Develop scanning algorithm

[darozak]

I need to develop a scanning algorithm that robots can use to generate a map of their current environment. This will involve:

1. Using the midpoint circle algorithm to plot a circle around the robot, which represent the maximum range of its scan, and using this to create a list of all the grid points on this circle.
2. Using Bresenham's line algorithm to trace a line from the robot to each of the grid points on the circle and following the line outward to identify each visible object along the path.
3. Following the scan line until it meats an impenetrable object or reaches the outer scan circle.
4. Presenting this information to the user as a 2D array of detected object IDs. Zeros will be used to mark unscanned points on the grid.

[darozak]

I found a compact JavaScript shadow casting algorithm that might be helpful. There is also a short article that describes the algorithm.

[darozak]

Here's a wiki that presents different field of vision algorithms in Python.

[darozak]

Here's a Roguelike JS toolkit with an FOV algorithm.

[darozak]

Imported lightsourse.js from here and am hoping I can adapt it to work with my code (https://gist.github.com/ebonneville/4200578).

[darozak]

Removed lighthouse.js and imported fov code from rot.js because these are more complete and appear to be stand-alone (https://github.com/darozak/Advolition/commit/44dbd02760af17b8c3b1abcd8f4fb943e29edd86).

I now need to see if I can use the classes to generate an fov map.

[darozak]

Looks like I got the shadow casting routine to work! (https://github.com/darozak/Advolition/commit/af4414b46dde4a187b4f9b3297bcfc2735a25524) However, I get an area when the radius of the light beam falls outside of the map grid. I need to find out how to bound the output so it doesn't exceed the array.

[darozak]

Adding if statements to ensure that the x and y values returned by the fov routine were not outside the bounds of the map arrays worked! (https://github.com/darozak/Advolition/commit/edcb0b3e083af365d2b0d73969e5bd3a923218b7). Right now the shadow casting arrays are being applied to dummy data. Next, I need to get the arrays working with game data.

[darozak]

By the way, here is a very helpful manual for implementing any of the routines in rot.js: https://ondras.github.io/rot.js/manual/#intro

[darozak]

The fov compute function now accepts a Boolean mask array which tells the algorithm which tiles allow the light from the scan to pass through them. (https://github.com/darozak/Advolition/commit/6470d90702bab8fbfc140c01bc86939923b462d0). This eliminates the need to pass a callback function to the fov constructor.

Next, I need to see if I can improve the way the fov compute function returns the scan results.

[darozak]

I further revised the fov compute function so that it returns the visibility results as a 2D number array rather than sending the results back via a reach back function (https://github.com/darozak/Advolition/commit/61ed5f6972110e3490e992669b54da789c5d85b8).

Next, I need to update the Dungeon class so that it can be prompted to generate a scan result and post it in the player's status.

[darozak]

I organized info on the hero and map grid into separate classes (https://github.com/darozak/Advolition/commit/4045ed421a9b093737744b9f154f95a250791977).

[darozak]

Further consolidated the code by converting the Dungeon class to a more general Grid class (https://github.com/darozak/Advolition/commit/7b88d4b749cc6a9d46bf3fd3583ce270cd7ab0d8).

[darozak]

I'm going to set this up so that the scan function will return a cloned layered array of the current scan. It will then be up to the player to decide what to do with the data. This will help to better compartmentalized the different game functions and leave it up to the player to determine a solution to the data that they're receiving.

[darozak]

The Grid scan function will now return an independent layered array of tile and npc IDs for the player robot to process as it sees fit. A negative value indicates that the grid wasn't scanned. (https://github.com/darozak/Advolition/commit/317e6c0be16c99b00ebb74380237512a5d16694f).

All I need to do now is plug the scan function into the Action class so that the player robot can request that scans be performed and receive the results.

[darozak]

Now the robot can add a scan action to the Action log and receive a scan update when the scan is complete (https://github.com/darozak/Advolition/commit/b74430e338d4a76b5bea3e33788781da727190c8). This successfully completes this task!