Sachverhalt:
A.
A.X._ und B.X._ sind Miteigentümer eines Grundstückes am Luxburgweg in der Gemeinde Egnach im Kanton Thurgau. Gemäss einem kantonalen Strassenprojekt ist zwischen Romanshorn und Egnach eine neue Linienführung des Seeradweges geplant. Zugleich soll der bisherige Wanderweg im Gebiet Egnach verlegt und neu über das Grundstück von A.X._ und B.X._ geführt werden.
A.X._ und B.X._ erhoben während der öffentlichen Auflage des Strassenprojektes vom 24. Juni bis 14. Juli 2011 beim Departement für Bau und Umwelt des Kantons Thurgau Einsprache. Mit Entscheid vom 5. Juni 2012 wies das Departement die Einsprache ab, soweit es darauf eintrat. Zur Begründung führte es im Wesentlichen aus, entlang des Bodensees seien die Wege für Wanderer einerseits und für Velofahrer bzw. Skater andererseits zu entflechten. Der bestehende Radweg in Egnach verlaufe ausschliesslich auf Gemeindestrassen, welche zum Teil stark von motorisierten Verkehrsteilnehmern beansprucht würden. Deshalb sei der bestehende Wanderweg zwischen dem Aachweg und der Luxburgstrasse zum Radweg auszubauen und der Wanderweg neu über den Luxburgweg zu führen. Das Projekt entspreche den Vorgaben des kantonalen Richtplanes und sei geeignet, die Verkehrssicherheit für alle Verkehrsteilnehmer zu erhöhen und gleichzeitig die Attraktivität der Seeroute zwischen Egnach und Romanshorn für Touristen zu steigern.
Mit Eingabe vom 27. Juni 2012 (Postaufgabe) erhoben A.X._ und B.X._ gegen diesen Entscheid beim Verwaltungsgericht des Kantons Thurgau "vorsorglich" Beschwerde mit den Anträgen, der Einspracheentscheid vom 5. Juni 2012 und das Strassenprojekt Romanshorn - Egnach seien aufzuheben; zudem sei das Beschwerdeverfahren bis zum Abschluss ihrer Verhandlungen mit der Firma Y._ AG über die Abtretung von Teilen angrenzender Parzellen zu sistieren. Zur Begründung führten A.X._ und B.X._ aus, sie hätten grundsätzlich "keine Einwände gegen das Strassenprojekt Seeradweg mit impliziertem Wanderweg Projekt"; um jedoch einen Ausgleich für die Abtretung ihres Landes an den Wanderweg zu erhalten, würden sie noch in Verhandlungen mit der Firma Y._ AG als Eigentümerin angrenzender Parzellen eintreten.
Am 15. August 2012 führte das Verwaltungsgericht einen Augenschein durch.
Mit Urteil vom 31. Oktober 2012 wies das Verwaltungsgericht die Beschwerde von A.X._ und B.X._ ab.
B.
Mit Eingabe vom 13. Januar 2013 führen A.X._ und B.X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht mit den Anträgen, das Urteil des Verwaltungsgerichtes vom 31. Oktober 2012 aufzuheben, die Linienführung des Wanderweges Romanshorn - Arbon im Gebiet der Gemeinde Egnach neu festzulegen und die Sache insoweit zu neuer Entscheidung an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht stellt den Antrag, die Beschwerde sei abzuweisen, soweit darauf eingetreten werden könne. Die Gemeinde Egnach beantragt, auf die Beschwerde sei nicht einzutreten. Die Vernehmlassungen wurden den Beschwerdeführern zugestellt.

Erwägungen:
1.
1.1. Der angefochtene Entscheid betrifft ein Strassenprojekt (Rad- und Wanderweg). Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-law>). Ein Ausschlussgrund nach <ref-law> besteht nicht. Angefochten ist ein Entscheid einer letzten kantonalen Instanz (<ref-law>). Die Beschwerdeführer haben am Verfahren vor der Vorinstanz teilgenommen. Sie sind als Eigentümer eines von der neuen Wanderwegführung betroffenen Grundstücks durch den Entscheid der Vorinstanz besonders berührt und haben ein schutzwürdiges Interesse an dessen Aufhebung (<ref-law>).
1.2.
1.2.1. Die Beschwerde ist nur im Rahmen des Streitgegenstandes zulässig. Dieser wird durch den Gegenstand des angefochtenen Entscheides und durch die Parteibegehren bestimmt, wobei der angefochtene Entscheid den möglichen Streitgegenstand begrenzt (<ref-ruling> E. 3.3 S. 189). Neue Begehren, d.h. solche, die vor der Vorinstanz nicht oder nicht mehr gestellt wurden, sind vor Bundesgericht unzulässig (vgl. <ref-law>).
1.2.2. Die Vorinstanz hat im angefochtenen Entscheid erwogen, bei dem von den Beschwerdeführern offenbar beabsichtigten Erwerb von Parzellenteilen, welche im Eigentum der Y._ AG stünden, handle es sich um eine rein privatrechtliche Angelegenheit, die für die Frage der Rechtmässigkeit des Strassenprojektes nicht relevant sei. Die Vorinstanz hat weiter ausgeführt, im Rahmen des Einspracheverfahrens hätten die Beschwerdeführer noch eine veränderte Linienführung (über die Luxburg- und Hafenstrasse und über das Gelände des Seeclubs) verlangt. Ein entsprechendes Begehren sei jedoch im verwaltungsgerichtlichen Verfahren nicht mehr gestellt worden. Hingegen hätten die Beschwerdeführer Bedenken bezüglich des Zuganges zum Aach-Bach geäussert, falls der Wanderweg wie geplant realisiert werden sollte. Am Augenschein habe sich jedoch gezeigt, dass der Zugang zum Bach auch nach Erstellung des Wanderweges weiterhin gewährleistet sein werde. Zusammenfassend erweise sich die Beschwerde als unbegründet.
1.2.3. In ihrer Beschwerde ans Bundesgericht halten die Beschwerdeführer eingangs fest, dass sie sich "nicht mehr auf privatrechtliche Servitute, unter anderem auf die Gefahr des Verlustes des Zuganges zum Bach" berufen würden, und dass sie "nicht mit dem eventuell beabsichtigten Erwerb von weiteren Parzellen" argumentieren würden. Sie verfolgten "einzig und allein die Änderung der Linienführung des geplanten Wanderweges über ihr Privatgrundstück" und beriefen sich dabei auf die allgemeinen und fundamentalen Regeln des Verwaltungsrechtes, nämlich auf das Gebot der Erforderlichkeit, das Gebot der Verhältnismässigkeit und auf die Anwendung des Übermassverbotes (Beschwerde S. 3).
1.2.4. Da die Beschwerdeführer somit "einzig und allein die Änderung der Linienführung des geplanten Wanderweges über ihr Privatgrundstück" verfolgen, welche nicht Gegenstand des vorinstanzlichen Entscheides gebildet hat, erweist sich das neue Begehren, die Linienführung des Wanderweges sei im Gebiet der Gemeinde Egnach neu festzulegen, als unzulässig. Die im vorinstanzlichen Verfahren strittigen Punkte (Zugang zum Bach, Erwerb von Parzellenteilen) fechten die Beschwerdeführer hingegen ausdrücklich nicht an. Auf die Beschwerde kann deshalb nicht eingetreten werden.
2.
Bei diesem Ausgang des Verfahrens sind die Gerichtskosten den Beschwerdeführern aufzuerlegen (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, der Politischen Gemeinde Egnach, dem Departement für Bau und Umwelt des Kantons Thurgau und dem Verwaltungsgericht des Kantons Thurgau schriftlich mitgeteilt.
Lausanne, 19. Juli 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Stohner