Navmesh awkward path generation with string pulling due to “inner” vertices

I’ve identified a problem and a possible solution related to navmesh-based pathfinding. Before diving in, I’ll preface my post with some questions to keep in mind as you read:

  • Is this a known problem that people have solved before?
  • Is there a term for the problem that could help me search for information related to it?
  • Is the solution I came up with an existing idea? If so is there a name for the algorithm or some other search term I could use to find more information?
  • Is there a better solution? If so, please point me to it.

For reference, I’m using images from http://jceipek.com/Olin-Coding-Tutorials/pathing.html#navigation-meshes and generally following the advice laid out there.

tl;dr of that blog post is

Decompose your walkable area into a navmesh, treating convex polygons as nodes and their borders as edges so that you can perform an A* search to get from point A to point B. To translate from “node ids” back to real points, use string-pulling.

Here’s a copy of the example space: initial example area

And an example generated path after performing string pulling: example area with a completed path from A to B

So far so good.

But I realized this approach generates an awkward path in a situation like this: awkward path

In this situation, a trio of nodes are all adjacent to each other, and so the A* will generally choose a path directly from the starting node to the ending node, despite an intuitive understanding that the agent can move in a straight line from A to B which travels through a different polygon.

I’ve been working on a solution to this problem and so far my best idea is to apply a transformation to the nav mesh. My description of this will be a little hazy as I’m making up terminology to describe the approach…

  • Define a shared edge as a line segment that is shared by two convex polygons in the navmesh. Maybe a.k.a. a “portal” for string-pulling purposes.
  • Define an inner vertex as a vertex in the navmesh for which all attached line segments are “shared edges”. The vertex in the center of the three polygons in the image above is an inner vertex.
  • Identify an inner vertex. Follow its attached shared edges to what I’ll call neighbor vertex. (possible improvement; If the neighbor vertex is also an inner vertex, recurse to its neighbors until all of the neighbors are non-inner.)
  • Remove all shared edges from the navmesh that were traversed in the previous step, forming a new polygon whose border is defined by the neighbor vertices in the previous step. Redefine the edges accordingly (I’ll hand-wave that)
  • Repeat until no inner vertices remain.

The result of this on the example above should result in this:

Transformed navmesh

And with the same A-B path from before, the string-pulling should now result in a straight line:

Transformed navmesh with fixed path planning

I believe that as long as the navmesh has no inner vertices, all paths generated with the approach described in the linked blog post should seem “natural” and not have any surprise corners in what seems like open space.

Per my questions at the beginning of this post, I’m looking for more information, e.g. has anybody else solved this problem before, is there a better way to do it, and is there even a name/term for this problem?

Random variate generation in Type-2 computability

Is there any existing literature on applying the theory of Type-2 computability to the generation of random variates? By “random variate generator” I mean a computable function $ f\colon\subseteq\{0,1\}^{\omega}\rightarrow D$ such that, if $ p$ is a random draw from the standard (Cantor) measure on $ \Sigma^{\omega}$ , then $ f(p)$ is a random draw from a desired probability distribution on $ D$ . Think of $ f$ as having access to an infinite stream of random bits it can use in generating its output value. Note that $ f$ need not be a total function, as long as its domain has (Cantor) measure 1.

It seems to me that the way to proceed would be to require that one specify a topology on $ D$ , in fact a computable topological space [1] $ \boldsymbol{S}=(D, \sigma, \nu)$ where $ \sigma$ is a countable subbase of the topology and $ \nu$ is a notation for $ \sigma$ , and use the standard representation $ \delta_{\boldsymbol{S}}$ of $ \boldsymbol{S}$ . One might also want membership in the atomic properties $ A\in\sigma$ to be “almost surely” decidable; that is, there is some computable $ g_A\colon\subseteq\{0,1\}^{\omega}\rightarrow\{0,1\}$ whose domain has measure 1, such that

$ $ g_A(p) = 1 \mbox{ iff } f(p)\in A$ $

whenever $ p\in\mathrm{dom}(g_A)$ .

I’m working on a problem that needs a concept like this, and I’d rather not reinvent the wheel if this is a concept that has already been well explored.

[1] See Definition 3.2.1 on p. 63 of Weihrauch, K. (2000), Computable Analysis: An Introduction.

Problem generation CSR in windows 10 with openssl

Currently, I have openssl 1.1.1.g running on a Windows 10 system.

I have to generate a new CSR with a key, but somehow it shows up with an error. I can’t seem to find out why, I think it has to do with windows 10. My IT guy said they no experience with openssl on windows systems, unfortunately in this specific case i am forced to use windows 10.

They gave me the following command, I think i get the error due the -config path. My location of OPENSSL = C:\OpenSSL-Win64\bin

Even when I try to change it in the config I get an error in Req.

Someone knows the cause?

openssl req -new -newkey rsa:2048 -nodes -out test.csr -keyout test.key -subj '/C=NL/ST=West-Province/L=Ci ty/O=Test of Organisation/OU=LMAO/CN=test.domain.com/' -reqexts SAN -extensions SAN -config <(cat /etc/ssl/openssl.cnf <(printf "[SAN]\nsubjectAltName=DNS:test.domain.com")) 

pkcs12 generation for EC key types using javascript

I’m generating p12 for EC keytypes using Forge library. https://github.com/digitalbazaar/forge/issues/777

This library already providing p12 for RSA key types, Now, I’m trying to enhance to ECC keytypes.

  1. Generating pem format Privatekey, certs into asn1 format private key. Here I’ve written ECPrivateValidator to validate and convert into asn1 format private key.
  class: asn1.Class.UNIVERSAL,   tag: asn1.Type.SEQUENCE,   capture: 'privateKeyInfo',   value: [{     name: 'PrivateKeyInfo.Version',     class: asn1.Class.UNIVERSAL,     tag: asn1.Type.INTEGER,     capture: 'privateKeyVersion'   }] }``` Can you guide me if you have any thoughts on it? 

Explanation of O(n2^n) time complexity for powerset generation

I’m working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward:

def power_sets(A):     """Returns the power set of A as a list of lists"""      if len(A) == 0:         return [[]]      else:         ps_n1 = power_sets(A[:-1]) # Powerset of set without last element         # Add nth element to each subset of the powerset of n-1 elements         ps_n = [sub + [A[-1]] for sub in ps_n1]          # Combine the two sets and return          return ps_n1 + ps_n 

It’s clear that the space complexity is $ O(n2^n)$ , since there are $ n$ items in the set, and each element is in half of the $ 2^n$ sets.

However, the book that I’m working from says the time complexity is also $ O(n2^n)$ , which makes perfect intuitive sense, but I’m having a hard time justifying it mathematically.

Other than by saying “there are x number of items to mess with, so time complexity is at least as much”, can anyone offer an explanation of the runtime analysis based on the runtime of the statements in my algorithm?

This answer pretty much only says that the runtime is such because of the space complexity (not very satisfying, but as an aside–can the runtime ever be better than the space complexity?)

I saw this answer, but to be honest it is a bit difficult to understand. It seems to suggest in the last line that the runtime is $ O(n^2*2^{n!})$ (since (I think) $ |P_i| = 2^i$ ), and that doesn’t seem right either.

I tried drawing out the call tree and that didn’t help, as there are only $ n-1$ recursive calls made, and from what I can tell each spends $ O(n^2)$ time.

Anyway, can someone offer a compelling explanation for this runtime?

Will extra rules to my diceware list generation scheme decrease security?

I finished reading the Code Book by Simon Singh, I’m interested in playing with some of the ideas in the book to help increase my own understanding. I don’t intend to implement the following in any consequential settings; I’m only interested in exploring the security implications.

I want to generate alternate diceware lists that have quirks, like each word is typed with the left hand only, or keystrokes alternating hands when typing. Assuming I can generate 7776 different strings, and am able to follow all of the other guidelines of diceware, are all diceware lists equally secure?

In the German Enigma Machine no letter could be encoded to itself (ex, a cannot be encoded to a). This detail helped crack the code. However I don’t think this applies here, the strength of the password doesn’t rely on a cipher. I don’t see why 6 or 7 strings randomly chosen from a list of 7776 wouldn’t have the same entropy, no matter the list. Theoretically, it could just consist of 7776 different binary lines couldn’t it?

I understand that additional rules to password generation sometimes decrease security. If an attacker knows my diceware list, does it matter if every entry consists of only 15 unique characters of the left hand? Is there less entropy?

Map Generation Biome – 3D Zonation Altitude/Temperature/Moisture

I’m working on an endless map generator and I have a question about biomes selection.

I already have all the work done to generate PerlinNoise (actually for map height and moisture) but every graph I found take only account of Temperature/Moisture. (Or sometime Latitude/Moisture but as i’m into an Endless map do not exist).

Example found on Google:

enter image description here enter image description here

Questions

  • Do I can assume that height of the map represent the temparature ? So high level are always cold and under snow, but sea level are always desert.
  • Do I need another noise (for Temperature) and found a 3D table to select biome (I didn’t found any) ??

Holdridge life zones

I also found a kind of 3D Zonation with Holdridge life zones but I don’t see how the 3 axis works.. enter image description here

I don’t see how to implement my 3 axis into this (Image (1)).

I also try (into Image (2)) to create a 3D version of it, but using triangular force me to handle High as Cold and Dry ?

So I think my real need is a simple 3D axis representing all cases between [0;1] (Image (3)) but I never saw stuff like that ??

enter image description here

Any ideas ?

Is there an official treasure generation method to limit magic item rolls based on dungeon level or some other factor?

I’m running an AD&D campaign for a party of usually-three PCs, who were first level until our most recent session. (As for what they are now, we’ll get to that…) I have the 1e DMG (door cover) and Unearthed Arcana, and a Monster Manual that might be older than that, judging by its condition. The players are using the 2e PHB; these are all inherited books, and the previous owner only ever DM’d in 1e and PC’d in 2e.

My issue is with treasure generation– I’ve been using the standard dungeon generation tables from the DMG, and it works well except for the outcome of treasure rolls. Specifically, magic items don’t seem to be segregated by dungeon level. That first-level party happened upon a Mirror of Mental Prowess, which had some fairly powerful effects but nothing game-breaking, and was worth five thousand experience. Divided among the party, this alone was enough to bring the priest and rogue to second level. Combined with the remainder of the treasure, those two reached level three, and the ranger reached level two.

Now building a dungeon for a later adventure, another magic item roll came up, resulting in… a Ring of Three Wishes. I simply vetoed that and re-rolled, getting something more reasonable this time, but now the question is in my mind of whether this is actually correct.

So, the simple version of the question:
Is there a method in AD&D to limit magic item rolls for treasure based on dungeon level or some other factor, or does this need to be created manually by the DM?


Note that this is not the same question as “What can I do when I accidentally gave out an overpowered item?” This relates purely to the RAW methods for generating magical treasures.