diff options
Diffstat (limited to '_site/log')
| -rw-r--r-- | _site/log/index.html | 13 | ||||
| -rw-r--r-- | _site/log/matrix-digital-rain/index.html | 125 | ||||
| -rw-r--r-- | _site/log/neo4j-a-star-search/index.html | 370 |
3 files changed, 446 insertions, 62 deletions
diff --git a/_site/log/index.html b/_site/log/index.html index 32f0ff2..4296fb7 100644 --- a/_site/log/index.html +++ b/_site/log/index.html @@ -174,6 +174,19 @@ + <tr> + <td class="posts-td posts-td-link"> + <a href="/log/neo4j-a-star-search/" class="link-decor-none">Neo4J A* search</a> + </td> + <td class="posts-td posts-td-time"> + <span class="post-meta"> + <time datetime="2018-03-06 00:00:00 +0800">2018-03-06</time> + </span> + </td> + </tr> + + + </table> </div> diff --git a/_site/log/matrix-digital-rain/index.html b/_site/log/matrix-digital-rain/index.html index 6007da5..4a23d29 100644 --- a/_site/log/matrix-digital-rain/index.html +++ b/_site/log/matrix-digital-rain/index.html @@ -44,40 +44,60 @@ <h2 class="center" id="title">RECREATING THE MATRIX RAIN WITH ANSI ESCAPE SEQUENCES</h2> <h6 class="center">21 DECEMBER 2025</h5> <br> - <div class="twocol justify"><p>The Matrix digital rain implemented in raw C using ANSI escape sequences with -zero dependencies—not even ncurses.</p> - -<video style="max-width:100%;" controls="" poster="poster.png"> - <source src="matrix.mp4" type="video/mp4" /> -</video> + <div class="twocol justify"><p>My 2022 implementation of the Matrix rain had too many loose ends. Unicode +support was inflexible: the charset had to be a single contiguous block with no +way to mix ASCII with something like Katakana; Phosphor decay level was stored +in a dedicated array–still don’t understand why I did that when I had already +used bit-packing for the RGB channels; The algorithm was difficult to decipher. +The 2022 version worked, but that’s not the same thing as being correct.</p> + +<p>I began by placing the decay factor in the LSB of the 4-byte RGB value. Let’s +call that RGB-PD. PD plays a somewhat analogous role to an alpha channel; I +avoided labelling it A so as not to cause confusion:</p> + +<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>enum { + R, /* Red */ + G, /* Green */ + B, /* Blue */ + PD /* Phosphor decay level */ +}; -<p>This is a fork of Domsson’s unique rendition of the Matrix rain: <a href="https://github.com/domsson/fakesteak" class="external" target="_blank" rel="noopener noreferrer">Fakesteak</a>. Three years ago, I forked his project -and added truecolor and Unicode support. I also drastically modified the -algorithm to produce a rain that resembled the original aesthetic with high -visual fidelity.</p> +typedef union color_tag { + uint32_t value; + unsigned char color[4]; +} color; +</code></pre></div></div> -<h2 id="unicode-support">Unicode support</h2> +<p>The decision to use union over more portable bit twiddling was made three years +ago, as I recall, for readability. Seeing as all my systems are little-endian, +this is unlikely to cause me trouble. Besides, if union is never to be used, +why is it in the language anyway?</p> -<p>Unicode support in the 2022 version lacked flexibility. The charset used in the -rain had to be a single contiguous block defined by <code class="language-plaintext highlighter-rouge">UNICODE_MIN</code> and -<code class="language-plaintext highlighter-rouge">UNICODE_MAX</code> settings:</p> +<p>The blend() function, which emulates the dim afterglow of Phosphor by eroding +the RGB channels towards the background, remains as elegant as it did three +years ago:</p> -<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>#define UNICODE_MIN 0x0021 -#define UNICODE_MAX 0x007E +<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>#define DECAY_MPLIER 2 -static inline void insert_code(matrix *mat, - size_t row, size_t col) +static inline void blend(matrix *mat, + size_t row, size_t col) { - mat->code[index(mat, row, col)] = rand() - % (UNICODE_MAX - UNICODE_MIN) - + UNICODE_MIN; + unsigned char *color; + + color = mat->rgb[index(mat, row, col)].color; + color[R] = color[R] - (color[R] - RGB_BG_RED) / DECAY_MPLIER; + color[G] = color[G] - (color[G] - RGB_BG_GRN) / DECAY_MPLIER; + color[B] = color[B] - (color[B] - RGB_BG_BLU) / DECAY_MPLIER; } </code></pre></div></div> -<p>There was no way, for instance, to use both ASCII and Katakana at the same -time. The user had to pick one. In the new version, the user can use any number -of Unicode blocks using <code class="language-plaintext highlighter-rouge">glyphs</code> array. In fact, the default rain now includes -both ASCII and half-width Katakana characters:</p> +<p>While the memory inefficiency of Phosphor decay tracking was a technical +oversight I hadn’t noticed, the limitation around mixing nonadjacent Unicode +blocks was a nagging concern even three years ago. So, a fix was long overdue.</p> + +<p>In the new version, I introduced a glyphs array that enables a user to add as +many Unicode blocks as they want. The insert_code() function picks a block +from the array at random, and then picks a character from that block at random:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>#define UNICODE(min, max) (((uint64_t)max << 32) | min) @@ -104,51 +124,32 @@ static inline void insert_code(matrix *mat, } </code></pre></div></div> -<p>Entries in the <code class="language-plaintext highlighter-rouge">glyphs</code> array are Unicode blocks bit-packed in an 8-byte -container: the four low bytes forms the first codepoint and the four high bytes -the last.</p> - -<h2 id="phosphor-decay">Phosphor decay</h2> +<p>The Unicode blocks are stored in 8-byte containers: the low four bytes form the +first codepoint and the high four bytes the last. Here, I chose bitwise +operations over unions because, first and foremost, the operations themselves +are trivial and idiomatic, and the UNICODE() macro simplifies the management of +charsets. The insert_code() function is now ready to take its rightful place +next to blend().</p> -<p>The dim afterglow of monochrome CRT displays is achieved by carefully scaling -the RGB channels individually and mixing them:</p> - -<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>#define DECAY_MPLIER 2 - -static inline void blend(matrix *mat, - size_t row, size_t col) -{ - unsigned char *color; - - color = mat->rgb[index(mat, row, col)].color; - color[R] = color[R] - (color[R] - RGB_BG_RED) / DECAY_MPLIER; - color[G] = color[G] - (color[G] - RGB_BG_GRN) / DECAY_MPLIER; - color[B] = color[B] - (color[B] - RGB_BG_BLU) / DECAY_MPLIER; -} -</code></pre></div></div> - -<p>The blending function emulates the phosphor decay by gradually transitioning -each raindrop’s color towards the background color. The multiplier is the -number of passes over the rain track needed before the afterglow disappears.</p> - -<h2 id="the-algorithm">The algorithm</h2> - -<p>Nonetheless, the rain resembles the original with high visual fidelity. It’s -highly customizable and gentle on the CPU. On my 14” ThinkPad T490, which has a -resolution of 1920x1080 and 4GHz CPU, it uses 2-3% of the CPU with occasional -jumps of up to about 8%. Not too bad for a weekend project. The program has -been tested with xterm and urxvt terminal emulators on OpenBSD and Arch Linux -systems. Someone has managed to get it moving on a Raspberry Pi as well.</p> - -<p>Lastly, to compile and run:</p> +<p>The result is a digital rain that captures the original Matrix aesthetic with +high visual fidelity:</p> <div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>$ cc -O3 main.c -o matrix $ ./matrix </code></pre></div></div> -<p>“All I see is blonde, brunette, red head.”</p> +<video style="max-width:100%;" controls="" poster="poster.png"> + <source src="matrix.mp4" type="video/mp4" /> +</video> + +<p>There was no cause to measure the program’s performance characteristics +precisely; it’s gentle on the CPU. On my ThinkPad T490 running OpenBSD, which +has a resolution of 1920x1080, it uses about 2-3% of the CPU, with occasional +jumps of up to about 8%; the cores remain silent, the fans don’t whir, the rain +falls in quiet.</p> <p>Files: <a href="source.tar.gz">source.tar.gz</a></p> + </div> <p class="post-author right">by W. D. Sadeep Madurange</p> </div> diff --git a/_site/log/neo4j-a-star-search/index.html b/_site/log/neo4j-a-star-search/index.html new file mode 100644 index 0000000..9473dc6 --- /dev/null +++ b/_site/log/neo4j-a-star-search/index.html @@ -0,0 +1,370 @@ +<!DOCTYPE html> +<html> + <head> + <meta charset="utf-8"> + <title>Neo4J A* search</title> + + <head> + <meta charset="utf-8"> + <meta name="viewport" content="width=device-width, initial-scale=1"> + <title>Neo4J A* search</title> + <link rel="stylesheet" href="/assets/css/main.css"> + <link rel="stylesheet" href="/assets/css/skeleton.css"> +</head> + + + + </head> + <body> + + <div id="nav-container" class="container"> + <ul id="navlist" class="left"> + + <li > + <a href="/" class="link-decor-none">hme</a> + </li> + <li class="active"> + <a href="/log/" class="link-decor-none">log</a> + </li> + <li > + <a href="/projects/" class="link-decor-none">poc</a> + </li> + <li > + <a href="/about/" class="link-decor-none">abt</a> + </li> + <li><a href="/feed.xml" class="link-decor-none">rss</a></li> + </ul> +</div> + + + + <main> + <div class="container"> + <div class="container-2"> + <h2 class="center" id="title">NEO4J A* SEARCH</h2> + <h6 class="center">06 MARCH 2018</h5> + <br> + <div class="twocol justify"><p>Back in 2018, we used <a href="https://neo4j.com/" class="external" target="_blank" rel="noopener noreferrer">Neo4J</a> graph database to track the +movement of marine vessels. We were interested in the shortest path a ship +could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling.</p> + +<p>A graph is a finite set of vertices, and a subset of vertex pairs (edges). +Edges can have weights. In the case of vessel tracking, the route points form +the vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel’s arrival time.</p> + +<p>Given a graph, an algorithm like Dijkstra’s search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J shipped with +at the time. One drawback of Dijkstra’s algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. The time complexity of this exhaustive search prevented our +database from scaling beyond 4,000 route points.</p> + +<p>The following enhancement to Dijkstra’s search, also known as the A* search, +employs a heuristic to steer the search in the direction of the destination +more quickly. In the case of our network of vessels, which are on the earth’s +surface, spherical distance is a good candidate for a heuristic:</p> + +<div class="language-plaintext highlighter-rouge"><div class="highlight"><pre class="highlight"><code>package org.neo4j.graphalgo.impl; + +import java.util.stream.Stream; +import java.util.stream.StreamSupport; + +import org.neo4j.graphalgo.api.Graph; +import org.neo4j.graphalgo.core.utils.ProgressLogger; +import org.neo4j.graphalgo.core.utils.queue.IntPriorityQueue; +import org.neo4j.graphalgo.core.utils.queue.SharedIntPriorityQueue; +import org.neo4j.graphalgo.core.utils.traverse.SimpleBitSet; +import org.neo4j.graphdb.Direction; +import org.neo4j.graphdb.Node; +import org.neo4j.kernel.internal.GraphDatabaseAPI; + +import com.carrotsearch.hppc.IntArrayDeque; +import com.carrotsearch.hppc.IntDoubleMap; +import com.carrotsearch.hppc.IntDoubleScatterMap; +import com.carrotsearch.hppc.IntIntMap; +import com.carrotsearch.hppc.IntIntScatterMap; + +public class ShortestPathAStar extends Algorithm<ShortestPathAStar> { + + private final GraphDatabaseAPI dbService; + private static final int PATH_END = -1; + + private Graph graph; + private final int nodeCount; + private IntDoubleMap gCosts; + private IntDoubleMap fCosts; + private double totalCost; + private IntPriorityQueue openNodes; + private IntIntMap path; + private IntArrayDeque shortestPath; + private SimpleBitSet closedNodes; + private final ProgressLogger progressLogger; + + public static final double NO_PATH_FOUND = -1.0; + + public ShortestPathAStar( + final Graph graph, + final GraphDatabaseAPI dbService) { + + this.graph = graph; + this.dbService = dbService; + + nodeCount = Math.toIntExact(graph.nodeCount()); + gCosts = new IntDoubleScatterMap(nodeCount); + fCosts = new IntDoubleScatterMap(nodeCount); + openNodes = SharedIntPriorityQueue.min( + nodeCount, + fCosts, + Double.MAX_VALUE); + path = new IntIntScatterMap(nodeCount); + closedNodes = new SimpleBitSet(nodeCount); + shortestPath = new IntArrayDeque(); + progressLogger = getProgressLogger(); + } + + public ShortestPathAStar compute( + final long startNode, + final long goalNode, + final String propertyKeyLat, + final String propertyKeyLon, + final Direction direction) { + + reset(); + + final int startNodeInternal = + graph.toMappedNodeId(startNode); + final double startNodeLat = + getNodeCoordinate(startNodeInternal, propertyKeyLat); + final double startNodeLon = + getNodeCoordinate(startNodeInternal, propertyKeyLon); + + final int goalNodeInternal = + graph.toMappedNodeId(goalNode); + final double goalNodeLat = + getNodeCoordinate(goalNodeInternal, propertyKeyLat); + final double goalNodeLon = + getNodeCoordinate(goalNodeInternal, propertyKeyLon); + + final double initialHeuristic = + computeHeuristic(startNodeLat, + startNodeLon, + goalNodeLat, + goalNodeLon); + + gCosts.put(startNodeInternal, 0.0); + fCosts.put(startNodeInternal, initialHeuristic); + openNodes.add(startNodeInternal, 0.0); + + run(goalNodeInternal, + propertyKeyLat, + propertyKeyLon, + direction); + + if (path.containsKey(goalNodeInternal)) { + totalCost = gCosts.get(goalNodeInternal); + int node = goalNodeInternal; + while (node != PATH_END) { + shortestPath.addFirst(node); + node = path.getOrDefault(node, PATH_END); + } + } + return this; + } + + private void run( + final int goalNodeId, + final String propertyKeyLat, + final String propertyKeyLon, + final Direction direction) { + + final double goalLat = + getNodeCoordinate(goalNodeId, propertyKeyLat); + final double goalLon = + getNodeCoordinate(goalNodeId, propertyKeyLon); + + while (!openNodes.isEmpty() && running()) { + int currentNodeId = openNodes.pop(); + if (currentNodeId == goalNodeId) { + return; + } + + closedNodes.put(currentNodeId); + + double currentNodeCost = + this.gCosts.getOrDefault( + currentNodeId, + Double.MAX_VALUE); + + graph.forEachRelationship( + currentNodeId, + direction, + (source, target, relationshipId, weight) -> { + double neighbourLat = + getNodeCoordinate(target, propertyKeyLat); + double neighbourLon = + getNodeCoordinate(target, propertyKeyLon); + double heuristic = + computeHeuristic( + neighbourLat, + neighbourLon, + goalLat, + goalLon); + + updateCosts( + source, + target, + weight + currentNodeCost, + heuristic); + + if (!closedNodes.contains(target)) { + openNodes.add(target, 0); + } + return true; + }); + + progressLogger.logProgress( + (double) currentNodeId / (nodeCount - 1)); + } + } + + private double computeHeuristic( + final double lat1, + final double lon1, + final double lat2, + final double lon2) { + + final int earthRadius = 6371; + final double kmToNM = 0.539957; + final double latDistance = Math.toRadians(lat2 - lat1); + final double lonDistance = Math.toRadians(lon2 - lon1); + final double a = Math.sin(latDistance / 2) + * Math.sin(latDistance / 2) + + Math.cos(Math.toRadians(lat1)) + * Math.cos(Math.toRadians(lat2)) + * Math.sin(lonDistance / 2) + * Math.sin(lonDistance / 2); + final double c = 2 + * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a)); + final double distance = earthRadius * c * kmToNM; + return distance; + } + + private double getNodeCoordinate( + final int nodeId, + final String coordinateType) { + + final long neo4jId = graph.toOriginalNodeId(nodeId); + final Node node = dbService.getNodeById(neo4jId); + return (double) node.getProperty(coordinateType); + } + + private void updateCosts( + final int source, + final int target, + final double newCost, + final double heuristic) { + + final double oldCost = + gCosts.getOrDefault(target, Double.MAX_VALUE); + + if (newCost < oldCost) { + gCosts.put(target, newCost); + fCosts.put(target, newCost + heuristic); + path.put(target, source); + } + } + + private void reset() { + closedNodes.clear(); + openNodes.clear(); + gCosts.clear(); + fCosts.clear(); + path.clear(); + shortestPath.clear(); + totalCost = NO_PATH_FOUND; + } + + public Stream<Result> resultStream() { + return StreamSupport.stream( + shortestPath.spliterator(), false) + .map(cursor -> new Result( + graph.toOriginalNodeId(cursor.value), + gCosts.get(cursor.value))); + } + + public IntArrayDeque getFinalPath() { + return shortestPath; + } + + public double getTotalCost() { + return totalCost; + } + + public int getPathLength() { + return shortestPath.size(); + } + + @Override + public ShortestPathAStar me() { + return this; + } + + @Override + public ShortestPathAStar release() { + graph = null; + gCosts = null; + fCosts = null; + openNodes = null; + path = null; + shortestPath = null; + closedNodes = null; + return this; + } + + public static class Result { + + /** + * the neo4j node id + */ + public final Long nodeId; + + /** + * cost to reach the node from startNode + */ + public final Double cost; + + public Result(Long nodeId, Double cost) { + this.nodeId = nodeId; + this.cost = cost; + } + } +} +</code></pre></div></div> + +<p>The heuristic function is domain-specific. If chosen wisely, it can +significantly speed up the search. In our case, we achieved a 300x speedup, +enabling us to expand our search from 4,000 to 13,000 route points. The <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" class="external" target="_blank" rel="noopener noreferrer">v3.4.0</a> of the +Neo4J graph algorithms shipped with our A* search algorithm.</p> + +</div> + <p class="post-author right">by W. D. Sadeep Madurange</p> + </div> + </div> + </main> + + <div class="footer"> + <div class="container"> + <div class="twelve columns right container-2"> + <p id="footer-text">© ASCIIMX - 2025</p> + </div> + </div> +</div> + + + </body> +</html> |