Way to show most recent descendants for someone without deep search?

jasonrohrer · 2018-05-14 20:06:16

I've updated the family tree browser to show Generation 1 for everyone, at the top of the tree view. So you always have a shortcut to Eve for any tree that you're looking at.

And since each character only has one Eve above them, this is easy to compute once and store per-person (who was their Eve? If we don't know yet, we can check if Eve is known for their parent and use that.... most of the time, we don't even need to walk all the way back to the root of the tree).

The other thing I would like to add is a "deepest descendant" row at the bottom of every tree view, showing how far a family has gotten. This would make it easy for you to check your latest descendants, for example, by searching for your character by name.

However, I cannot figure out an efficient way to do this, given that the depth of trees is potentially unbounded. I can't think of a way to do it that doesn't involve searching the entire family tree to visit all of the leaves, but I don't think I should be recomputing this every time someone is just browsing around, given that there could potentially be thousands or millions of leaves to visit, and each visit requires at least one MySQL query. The Boots family tree already has 600+ leaves, for example.

ryanb · 2018-05-14 20:27:29

What about using the generation number? You can find the highest generation matching the same eve.

SELECT * FROM lineageServer_lives WHERE eve_life_id = ? ORDER BY generation DESC LIMIT 1

However this won't show the deepest descendent of the selected player, only of that player's family.

Last edited by ryanb (2018-05-14 20:31:17)

pein · 2018-05-14 21:04:39

well you could add a random names/predefined names for the unnamed kids, and force people to choose unique family names,or just give an ID for each family, then a letter combination for generations, so game would store it on birth. this would give as a search result several leaves instead of a line of descendants. for selected player, each branch should have an id, so each mother considered a new family and only search that one. if i understand correctly.

its more complicated than a soap opera, some daughters die at 15, but their daughter is raised by someone else, good players outlive 4 generations, and even if you lived on a same time, can be a difference of 2-3 generations between you and a kid, now if this occurs a few times that a person is a highly skilled woman and reaches old age, her latest kids can be way below the generation number, but they are alive and a dead branch holds the record, so i guess people are more interested on youngest people alive of that family not the carrot farmer baby machines who die at first famine but their little locusts take over and do the same 15 minutes later. my bottom row of descendants are naked womans grandkids who starved before age 10, and all three generations die before me

Last edited by pein (2018-05-14 21:08:56)

zed · 2018-05-14 21:17:33

How about: store with each entry the current deepest descendent and its depth,
then when a death is logged recurse up through the maternal line of ancestors,
setting the newly dead descendent as the deepest while it is the deepest
(you can abort the recursion as soon as it isn't).

YAHG · 2018-05-14 22:57:17

I don't know how many families are running at any given time, I assume you have that data.

You could just store the recent decedents for each living family and update it on every birth/death
to minimize the queries?

I assume once the lines are extinguished you just dump it anyways.

Go! Bwah! · 2018-05-15 00:51:01

zed wrote:

How about: store with each entry the current deepest descendent and its depth,
then when a death is logged recurse up through the maternal line of ancestors,
setting the newly dead descendent as the deepest while it is the deepest
(you can abort the recursion as soon as it isn't).

My thought, too... but if only deaths are logged, won't this break if the deepest descendant pre-deceases an ancestor?

Seems like logging players at birth would fix this (as well as other family-tree weirdnesses - why does somebody need to be dead to be on the family tree?).

jasonrohrer · 2018-05-15 02:38:24

Yes, setting it when a descendant dies by walking all the way back to Eve is a great way to do it.

If one of the ancestors isn't dead yet, they won't get updated (because they don't exist in the table until they die). I suppose I could also do a small tree exploration down when anyone dies, to set their deepest descendant so far. That tree is guaranteed to not be very big at that time, because it's at most 4 generations deep, and I can cheat in that exploration by looking at the already-saved deepest descendant on this person's offspring.

Lily · 2018-05-15 02:49:22

You could do a full search for the newest descendant but only do it once per hour as long as the line hasn't died out. Then just pin it there, so it isn't created on the fly each time someone searches, just once an hour.

abliss · 2018-05-15 11:39:39

You could make a separate "ancestor-descendant" table, with an index on both its columns. When someone is born, you do a batch-insert of all their mother's ancestors, plus one more insert for their mother. Then you can do a single sql query joining this to the player table to get all descendants of X ordered by generationNumber.

jasonrohrer · 2018-05-16 19:24:07

This is working now. The deepest descendants are shown at the bottom of the family tree view.

Joriom · 2018-05-17 13:45:51

Why do it once per hour or store it for everyone?

Eve stays the same for each lineage and is transfered to every descendant, right? So everything bound to "Eve" is available for entrie lineage.

Store "highest generation number" (HGNo) and "highest generation members" (HGMe) with Eve.

When death for lineage is received - check relation between "Death Gen Num" (DGNo) and Eve HGNo.

if (DGNo < HGNo) skip
if (DGNo = HGNo) HGMe += current death entry (add next entry to the list - current)
if (DGNo > HGNo) HGMe = current death entry (clear it and reset with single entry - current)

HGNo could be stored:
a) in the same table as single field with clever trickery (would require additional parsing of that field every time)
b) or in sepearate table as few entries linked by foreign key. Eve could hold just hold reference number to relevant entries. (would require additional sql request every time)

In case of solution b) - you need to delete entries instead of resetting field... or you can just leave them without clearing creating sideeffect of being able to link and recall people who were "peak of their generation" every step before next gen was born. Would require additional linking and database size would increase faster.

When checking character_page, just get data from Eve entry and use it to get HGMe entries.

Last edited by Joriom (2018-05-17 13:46:55)

jasonrohrer · 2018-05-17 15:47:09

I want highest generation below each person, not just below Eve. You care about your descendants, not Eve's.

I've done this by adding two fields to each person: Deepest gen # and deepest gen person (some sibling in the deepest generation).

When you die, these are populated by a an initial tree search below you, which is guaranteed to be a small tree.

When someone else dies, the tree above them is walked up and updated, if their generation is deeper than the deepest known above them. This is a log(n) operation, where n is the family size.

This all happens in realtime, not once per hour.

Data storage is minimal, 8 bytes per person.

One Hour One Life Forums

#1 2018-05-14 20:06:16

Way to show most recent descendants for someone without deep search?

#2 2018-05-14 20:27:29

Re: Way to show most recent descendants for someone without deep search?

#3 2018-05-14 21:04:39

Re: Way to show most recent descendants for someone without deep search?

#4 2018-05-14 21:17:33

Re: Way to show most recent descendants for someone without deep search?

#5 2018-05-14 22:57:17

Re: Way to show most recent descendants for someone without deep search?

#6 2018-05-15 00:51:01

Re: Way to show most recent descendants for someone without deep search?

#7 2018-05-15 02:38:24

Re: Way to show most recent descendants for someone without deep search?

#8 2018-05-15 02:49:22

Re: Way to show most recent descendants for someone without deep search?

#9 2018-05-15 11:39:39

Re: Way to show most recent descendants for someone without deep search?

#10 2018-05-16 19:24:07

Re: Way to show most recent descendants for someone without deep search?

#11 2018-05-17 13:45:51

Re: Way to show most recent descendants for someone without deep search?

#12 2018-05-17 15:47:09

Re: Way to show most recent descendants for someone without deep search?

Board footer