News for hackers. Stuff that matters.
Re:Adventure Games and Eigenvalues (2017) by toxik on Tuesday June 18, 2019 @05:15AM (#20210881)
More precisely, construct a graph with vertices (u, v) where u is a prior state and v a possible successor state, then there must not be a node of out-degree zero unless it is an end state.

As far as complexity goes, this should be linear in number of vertices. In fact, you don't even really have to construct the graph, just count out degree.

Re:Adventure Games and Eigenvalues (2017) by akrasuski1 on Tuesday June 18, 2019 @06:27AM (#20211406)
That is not enough, since you may still get stuck in a loop.
Re:Adventure Games and Eigenvalues (2017) by toxik on Tuesday June 18, 2019 @01:09PM (#20215422)
Fair point, but that is inevitable unless it's a game where the user cannot go back, very few games would fit that bill then.