There is CJDNS (https://github.com/cjdelisle/cjdns/blob/master/doc/Whitepape...) which has distributed routing table and addressing based on public keys.

Traditional tables won't scale.

Have each node know it's position (lat/lon) and the position of it's nearest neighbors. When you send a packet, you send it to a lat/lon, and every node that sees your packet just tries to nudge it a little closer, until it gets there. Then to speed things up on the return trip we can ask each intermediate to add their position to a list on the packet.

Of course, moving nodes present a bit of a problem. Because they will keep attaching and detaching, there returning packets won't know where to reach them. I suppose if you knew your route through space you could send "scout" packets ahead of you, feel out the terrain, and prepend those positions to the list of your packets (so that they can find you when they return).

Dealing with changes to the (static) topology and also rogue nodes (ones that misbehave, drop packets, lying about their position, etc) are interesting problems. I think they can be solved.

I think geography is a red herring.

The addresses must have meaning and hosts must self organise into a subnet based on connectivity, which feels like a np-hard problem... That does not imply that there is no reasonably well working approximation that works more or less as good except for edge cases. (Literally, ha...)

No reason a spatial routing algorithm couldn't take connectivity into account. Indeed, this is a pretty straight-forward application of A*.

I came to think of molds and how they route networks with just local agents...

It might be, but you'd need to be smarter than me.

Maybe the problem is harder than it superficially seems, but assuming the network is not super sparse, sending things in the right geographical direction (GPS is ubiquitous) should be a very good heuristic. Couple it with exact routing information for the "neighborhood" (idk which radius would make sense) of a node, should be able to avoid going down a dead end most of the time.

here's a simple (very bad) example of distributed routing.

Addresses are simply bitstrings of some length.

If my address is a=a1a2...an, I need to store the first segment of the shortest path to each r_1=a'1a2...an, r_2=a1a'2...an all the way up to r_n=a1a2...a'2, where a'k != ak (i.e. all the addresses with a hamming distance of exactly 1 from me). I then simply route a message with an address b=b1b2...bn to r_i where i is the first non-zero bit of a xor b.

There is Kademlia, but it still needs to be improved to take geo distance and link quality into account, for it to work on a global scale.

There is Geodemlia, that routes by geographical distance and is based of Kademlia and its routing buckets.

The problem, as with most P2P-networks, is that its not resistant to high network churn.