## Coding Spelunky Edge Roll Mechanic

Inspired by the recently released Spelunky 2, I’ve been making Spelunky clone from scratch using Monogame for gamedev coding practice.

I’ve successfully coded the basic platforming mechanics: terrain collision solving, gravity, running and jumping, even having the camera pan up or down after pressing those buttons for a half-second.

The next thing I am trying to implement is edge-hanging. Getting the basic case of hanging after falling onto an edge in the right way was easy enough. I basically just checked for the right conditions and added a boolean in my player class for whether the player is hanging, which prevents left/right motion and keeps the player from falling when it’s true.

My question is: how can I implement the edge-rolling mechanism, where you can roll over edges into an edge-hang by pressing down as you walk off? I don’t understand what extra information I need to store or how to smoothly transition the player from being halfway on the edge to hanging off of the edge one block lower.

Right now the player just kind of falls away from the edge after walking off, as you would expect with the basic mechanics so far.

## In doubly connected edge list how to link halfedges properly

I’m working on doubly connected edge list. In the image below I need to add a new edge (consisting of halfedges $$g$$ and $$h$$). When adding a new edge we need to assign each half edge a previous and next half edges. In this example edge $$g$$ would have halfedge $$f$$ and $$h$$ as previous and next halfedges respectively. And edge $$h$$ would have halfedge $$g$$ and $$a$$ as previous and next halfedges respectively. If we ignore for a second them being linked to each other, $$g$$ and $$h$$ are linked to the pair $$f$$ and $$a$$. I hope this makes sense. My question is when adding a new edge, how do we know how to choose the correct pair to link to? In this example we could link our halfedges to the pair $$a, f$$ or $$c,b$$, or $$e,d$$. Do we have to resort to linear algebra, doing cross/dot product calculations to calculate what pair of halfedges to choose, based on the geometry of the edges? Am I possibly going in the completely wrong direction?

To get the potential canditates of pair of halfedges to link to, I iterate through all halfedges linked to vertex $$v$$, which here would be $$a,c,e$$ and for each I find the previous halfedge which would $$f, b,d$$ respectively.

## Understanding the proof of “DFS of undirected graph $G$, yields either tree edge or back edge” better with graph for each statement in proof

I was going through the edge classification section by $$\text{DFS}$$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. I was having a little difficulty in understanding the steps of the proof and hence I made an attempt to understand it fully by accompanying each statement in the proof with a possible graph of the situation.

Theorem 22.10 : In a depth-first search of an un-directed graph $$G$$, every edge of $$G$$ is either a tree edge or a back edge.

Proof:

1. Let $$(u , v)$$ be an arbitrary edge of $$G$$, and suppose without loss of generality that $$d[u] < d[v]$$. Then, $$v$$ must be discovered and finished before we finish $$u$$ (while $$u$$ is gray), since $$v$$ is on $$u$$‘s adjacency list.

2. If the edge $$(u, v)$$ is explored first in the direction from $$u$$ to $$v$$ , then $$v$$ is undiscovered (white) until that time.

Figure 1 : Situation in point 2. DFS starts from ‘u’, ‘u’ is grayed and DFS then looks along the red arrow to ‘v’

1. Otherwise we would have explored this edge already in the direction from $$v$$ to $$u$$. Thus, $$(u, v)$$ becomes a tree edge.

Figure 2 : Situation in point 3. DFS starts from ‘u’, ‘u’ is grayed, then discoveres ‘w’ and ‘w’ is grayed and then again discovers ‘v’ DFS then looks along the red arrow to ‘u’ , the green pointer explains the rest

1. If $$(u, v)$$ is explored first in the direction from $$v$$ to $$u$$, then $$(u, v)$$ is a back edge, since $$u$$ is still gray at the time the edge is first explored.

Figure 3 : Situation in point 4. DFS starts from ‘u’, ‘u’ is grayed, then discoveres ‘w’ and ‘w’ is grayed and then again discovers ‘v’ DFS then looks along the red arrow to ‘u’ , ‘u’ is already grayed so the edge becomes a back edge, indicated by the green pointer

Could anyone confirm if I am on the right track or if not please rectify me.

[My question might seem similar to this or this but neither of them seemed to help me]

## leetcode 10. Regular Expression Matching edge cases

Please tell me how to deal with edge case such as s:"aa", p:"a*"in else if (p[j] == '*') branch. One way I know is to increase the size of dp like vector<vector<bool>> dp(s.size() + 1, vector<bool>(p.size() + 1, false) ); However, in that case the index of dp will not be the same with the index of for loop.

The problem is as follows:
Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

'.' Matches any single character. '*' Matches zero or more of the preceding element. 

The matching should cover the entire input string (not partial).

Here is the code:

class Solution { public:     bool isMatch(string s, string p) {         vector<vector<bool>> dp(s.size(), vector<bool>(p.size(), false) );         dp[0][0] = (s[0] == p[0] ? true : false);                  for (int i = 1; i < s.size(); i++) {             for (int j = 1; j < p.size(); j++) {                 if (s[i] == p[j] || p[j] == '.') {                     dp[i][j] = dp[i - 1][j - 1];                 } else if (p[j] == '*') {                     dp[i][j] = dp[i - 1][j] || dp[i][j - 2];                 } else if (s[i] != p[j]) {                     dp[i][j] = false;                 }             }         }                  return dp[s.size() - 1][p.size() - 1];     } }; 

## Is there a function to, given a set of co-ordinates, return a list of co-ordinates on the edge [closed]

For example, return the coordinates (-1, 1) (0,0) (1,1) and (1,2) from the following cartesian plane

## Prove: If $T’$ is not a MST one of its edges may be replaced by a lighter edge in order to get a lighter spanning tree

Prove: If $$T’=(V,F’)$$ is not a MST of $$G=(V,E)$$, then there are edges $$e’ \in F$$ and $$e \in$$ $$E$$ \ $$F$$ such that $$w(e) and $$T’$$ \ $$\{e’\} \cup \{e\}$$ is a spanning tree.

My idea:

Let $$T=(V,F)$$ be a MST of $$G$$

for all $$e \in T$$, try to insert it into $$T’$$ and see if there is an edge in the cycle created that is heavier than $$e$$. If we found such $$e$$ we are done.

If not, define $$G’=(V,F \cup F’)$$

This graph obviously has a MST.

We didn’t find a suitable $$e$$ in the previous part so all edges in $$F$$ may be colored in red.

That means there is a MST $$T”=(V,F”)$$ such that $$F” \ F’$$ but that is impossible because $$T’$$ is not a MST of $$G’$$, because $$T$$ is lighter.

Does that seem correct?

## When would you use an edge list graph data structure instead of an adjacency list or adjacency matrix?

In what applications would you choose an edge list over an adjacency list or an adjacency matrix?

Sample Question, VisuAlgo: Which best graph DS(es) should you use to store a simple undirected graph with 200 vertices, 19900 edges, and the edges need to be sorted? Suppose your computer only has enough memory to store 40000 entries.

There are three choices: adjacency lists, adjacency matrix, and an edge list.

Edge lists are the correct answer here because sorting by weight is most efficient, but what are some other use cases?

Thanks!

## Find the probability of occurrence of each edge in a graph having $n$ nodes after $k$ operations

Given a graph with $$n$$ nodes . The adjacency matrix of the graph is given. We do $$k$$ operations on this graph. In each operation we choose two distinct nodes $$i$$ and $$j$$ (there are $$(n*(n-1))/2$$ such choices) equiprobably (all choices are equiprobable) and if there exists a edge between $$i$$ and $$j$$ we delete that edge or else we draw an edge between the chosen pair of nodes.
We have to output a $$n*n$$ matrix where the element at $$(i,j)th$$ position denotes the probability of occurrence of edge connecting the nodes $$i$$ and $$j$$ in the final resulting graph.
The constraints on n and k are $$n<=50$$ and $$k<=50$$ .
I tried it using dynamic programming but could figure out transitions properly.