For a personal project, I wanted to recreate rollback netcode(details below)

https://en.wikipedia.org/wiki/GGPO

I run into a problem with trying to get peers to connect with each other. If I run two instances of my program on the same machine, they connect just fine, but if I run two instances of the program on two different machines on the same router or different routers, they fail to connect. It seems that the problem has to do with NAT. A lot of my searches show that peer to peer solutions often use a relay server to get around this problem, but I wanted to know if it was possible to do peer to peer with out a relay server. Is this even possible and how?

Any help would be appreciated.

To make two machines behind different NAT's to communicate you will need some 3rd party server that is accessible by it's public IP.

Relay is common solution that forwards all the traffic through server.

Alternative is NAT punch-through where public server is involved only during initial handshake, but afterwards both behind-NAT machines can communicate directly without help server. Here's an article that looks reasonable and goes into more detail on this: https://bford.info/pub/net/p2pnat/

There are protocols like STUN that help p2p connections to establish direct connections. They are mostly used for audio/video streaming, for example, WebRTC.

Here are some simple code examples I found that does hole punching (but not sure how good they work, haven't run them):
https://github.com/ckennelly/hole-punch
https://github.com/mwarning/UDP-hole-punching-examples
https://github.com/povilasb/hole-punching
https://github.com/real-supadev/tcpholepunching

sorry for taking so long to reply. Thanks for all the infomation.